My elegant solution By using tire tree


  • 0
    Z

    Below is my AC code for this problem by using tire tree

    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;
    }
    };

  • 0
    L

    I don't see any benifit from trie tree. String comparsion is sufficient and clear.


Log in to reply
 

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