题解 | #最长公共前缀#

我以为是用前缀树，结果超内存，累了

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


class preTreeNode{
public:
    preTreeNode(int path,int end):path(path),end(end){}
public:
    preTreeNode* index[26] = {nullptr};
    int path = 0;
    int end = 0;
};


class PreTree{
public:
    void insert(string& word){
        preTreeNode* curr = root;
        for(int i = 0;i<word.size();++i){
            int t = int(word[i]-'a');
            if(curr->index[t]==nullptr){
                curr->index[t] = new preTreeNode(1,0);
            }
            else{
                curr->index[t]->path++;
            }
            if(i==word.size()-1){
                curr->index[t]->end++;
            }
            curr = curr->index[t];                                                                                                                                                                                   
        }
    }
    string findmaxPre(int size,string& str){
        string result = "";
        preTreeNode* curr = root;
        for(int i = 0;i<str.size();++i){
            int in = int(str[i]-'a');
            if(curr->index[in]->path==size){
                result += str[i];
            }
            else{
                break;
            }
            curr = curr->index[in];
        }
        return result;
    }
public:
    preTreeNode* root = new preTreeNode(0,0);
};


class Solution {
public:
    /**
     * 
     * @param strs string字符串vector 
     * @return string字符串
     */
    string longestCommonPrefix(vector<string>& strs) {
        // write code here
        if(strs.empty()){
            return "";
        }
        PreTree P;
        for(int i = 0;i<strs.size();++i){
            P.insert(strs[i]);
        }
        return P.findmaxPre(strs.size(),strs[0]);
    }
};


int main(){
    Solution S;
    vector<string> v = {"abca","abc","abca","abc","abcc"};
    cout<<S.longestCommonPrefix(v)<<endl;
}