Longest Common Prefix

Given k strings, find the longest common prefix (LCP).

http://www.lintcode.com/en/problem/longest-common-prefix/

Solution

O(kn)的解法很直观，一个个遍历string，看到哪一位上出现不同的字符就终止。

class Solution {
public:    
    /**
     * @param strs: A list of strings
     * @return: The longest common prefix
     */
    string longestCommonPrefix(vector<string> &strs) {
        string result;
        if(strs.empty()) return result;
        int id = 0;
        while(true) {
            if(id >= strs[0].size()) {
                break;
            }
            char pivot = strs[0][id];
            bool common  = true;
            for(int i=1; i<strs.size(); i++) {
                if(id >= strs[i].size() || strs[i][id] != pivot) {
                    common = false;
                    break;
                }
            }
            if(common == false) {
                break;
            }
            id++;
            result.append(1, pivot);
        }
        return result;
    }
};

更简洁的写法

string longestCommonPrefix(vector<string> &strs) {
        string commstr = "";
        if(strs.empty()) return commstr;
        for(int i=0; i<strs[0].size(); i++) {
            for(int j=1; j<strs.size(); j++) {
                if(strs[j].size() <=i || strs[j][i] != strs[0][i]) {
                    return commstr;
                }
            }
            commstr+=strs[0][i];
        }
        return commstr;
    }

Follow up

二分查找实现。

string longestCommonPrefix(vector<string> &strs) {
        string result;
        if(strs.empty()) return result;
        int min_len = INT_MAX;
        for(int i=0; i<strs.size(); i++) {
            if(strs[i].size() < min_len) {
                min_len = strs[i].size();
            }
        }
        int start = 0; 
        int end = min_len - 1;
        while(start + 1< end) {
            int mid = start + (end-start)/2;
            bool common  = true;
            for(int i=0; i<strs.size()-1; i++) {
                if(strs[i][mid] != strs[i+1][mid]) {
                    common = false;
                    break;
                }
            }
            if(common == false) {
                end = mid;
            } else {
                start = mid;
            }
        }
        for(int i=0; i<strs.size()-1; i++) {
            if(strs[i][end] != strs[i+1][end]) {
                return strs[0].substr(0, start+1);
            }
        }
        return strs[0].substr(0, end+1);
    }

Follow up again

还有个O(1)的解法，或者说O(m), m是最长common prefix的长度。利用输入的strings建立一个Trie。参考Add and Search word。