题解 | #最长公共前缀#

最长公共前缀

http://www.nowcoder.com/practice/28eb3175488f4434a4a6207f6f484f47

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

#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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 18:06
点赞 评论 收藏
分享
自学java狠狠赚一...:骗你点star的,港卵公司,记得把star收回去
点赞 评论 收藏
分享
05-29 20:34
门头沟学院 C++
KarlAllen:得做好直接春招的准备。学历差的话,一是面试要求会比学历好的严格不少,二是就算面试通过了也会被排序。总之暑期和秋招对于学历差的就是及其不友好
无实习如何秋招上岸
点赞 评论 收藏
分享
07-02 10:44
门头沟学院 C++
码农索隆:太实诚了,告诉hr,你能实习至少6个月
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务