My elegant solution By using tire tree


  • 0
    Z

    class Solution {
    private:
    class Node{
    public:
    Node* children[256];
    bool terminated;
    Node(){
    memset(children, 0 ,sizeof(Node*) * 256);
    terminated = false;
    }
    } *root,*current;
    public:
    string longestCommonPrefix(vector<string> &strs) {
    int size = strs.size();
    if(size<=0) return "";
    if(size==1) return strs[0];
    string commonPrefix = "";
    current = root = new Node();
    int len = strs[0].length();
    for(int i=0;i<len;i++){
    current = current->children[strs[0][i]] = new Node();
    }
    current->terminated = true;
    for(int i=1;i<size-1;i++){
    current = root;
    len = strs[i].length();
    for(int j=0;j<len && (!current->terminated && current->children[strs[i][j]] != NULL);current = current->children[strs[i][j++]]);
    current->terminated = true;
    }
    len = strs[size - 1].length();
    current = root;
    for(int j=0;j<len && (!current->terminated && current->children[strs[size-1][j]] != NULL);commonPrefix += strs[size-1][j], current = current->children[strs[size-1][j++]]);
    return commonPrefix;
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.