题解 | #最长公共前缀#

字典树

class Solution {
private:
    struct Trie{
        int cnt;
        Trie* next[26];
        Trie(){
            cnt = 0;
            for(int i = 0; i < 26; i ++) next[i] = NULL;
        }
    };
    Trie* root = new Trie();
public:
    /**
     * 
     * @param strs string字符串vector 
     * @return string字符串
     */
    string longestCommonPrefix(vector<string>& strs) {
        // write code here
        buildTrie(strs);
        int n = strs.size();
        string res;
        Trie* p = root;
        while(p != NULL){
            for(int i = 0; i < 26; i ++){
                if(p -> next[i] != NULL && p -> next[i] -> cnt == n){
                    res += i + 'a';
                    p = p -> next[i];
                    break;
                }
                if(i == 25) p = NULL;
            }
        }
        return res;
    }
    void buildTrie(vector<string>& strs){
        for(string str:strs){
            //cout << str << " ";
            helper(str);
        }
    }
    void helper(const string& str){
        Trie* p = root;
        for(char ch:str){
            int idx = ch - 'a';
            if(p -> next[idx] == NULL) p -> next[idx] = new Trie();
            p = p -> next[idx];
            p -> cnt ++;
        }
    }
};