您當前位置：首頁 > php開源 > php教程 > leetcode筆記：Longest Common Prefix

leetcode筆記：Longest Common Prefix

來源：程序員人生發布時間：2016-03-03 09:08:16 閱讀次數：2453次

1. 題目描寫

Write a function to find the longest common prefix string amongst an array of strings.

2. 題目分析

題目的大意是，給定1組字符串，找出所有字符串的最長公共前綴。

對照兩個字符串的最長公共前綴，其前綴的長度肯定不會超過兩個字符串中較短的長度，設最短的字符串長度為n，那末只要比較這兩個字符串的前n個字符便可。

使用變量prefix保存兩個字符串的最長公共前綴，再將prefix作為1個新的字符串與數組中的下1個字符串比較，以此類推。
1個特殊情況是，若數組中的某個字符串長度為0，或求得確當前最長公共前綴的長度為0，就直接返回空字符串。

3. 示例代碼

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) 
    {
        if (strs.size() == 0)
          return "";

        string prefix = strs[0];
        for (int i = 1; i < strs.size(); ++i)
        {
            if (prefix.length() == 0 || strs[i].length() == 0)
               return "";

            int len = prefix.length() < strs[i].length() ? prefix.length() : strs[i].length();

            int j;     
            for (j = 0; j < len; ++j)
            {
                if (prefix[j] != strs[i][j])
                    break;
            }
            prefix = prefix.substr(0,j);
        }
        return prefix;
    }
};