My AC solution using TrieTree and DFS with 5 ms, but i met a problem.


  • 1
    L

    all the test case is ok except one.

    dict = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};

    s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

    when i add a if condition like:

    if(s[0] == s[1])
        reverse(s.begin(),s.end());
    

    my solution is accepted.

    i know why this test case can lead to TimeLimited, but i have no idea to solve it. Help me.

    struct TrieNode{
        char val;
        bool isEnd;
        TrieNode* next[26] = {NULL};
        TrieNode(char x) : val(x), isEnd(false) {}
    };
    
    class TrieTree{
    private:
        TrieNode* root = new TrieNode('a');
    public:
        void trieInsert(string word){
            TrieNode* RootTemp = root;
            for(int i = 0; i < word.size(); i++){
                if(RootTemp->next[word[i]-'a'] == NULL){
                    RootTemp->next[word[i]-'a'] = new TrieNode(word[i]);
                    RootTemp = RootTemp->next[word[i]-'a'];
                }
                else{
                    RootTemp = RootTemp->next[word[i]-'a'];
                }
            }
            RootTemp->isEnd = true;
        }
        bool canBreak(string s){
            TrieNode* RootTemp = root;
            for(int i = 0; i < s.size(); i++){
                if(RootTemp->next[s[i]-'a'] != NULL){
                    RootTemp = RootTemp->next[s[i]-'a'];
                    if(RootTemp->isEnd == true){
                        if(i+1 == s.size()) return true;
                        if(canBreak(string(s,i+1,s.size()-i-1))) return true;
                    }
                }else return false;
            }
            return false;
        }
    };
    
    class Solution {
    public:
        TrieTree MyTrieTree;
        bool wordBreak(string s, unordered_set<string> &dict) {
            for(auto& word : dict){
                string wordtemp = word;
                if(s[0] == s[1])
                reverse(wordtemp.begin(),wordtemp.end());
                MyTrieTree.trieInsert(wordtemp);
            }
            if(s[0] == s[1])
            reverse(s.begin(),s.end());
            return MyTrieTree.canBreak(s);
        }
    };

  • 0
    W

    Well, I think your algorithm is lucky to pass the OJ because the test case didn't cover like bbaaaaaaaaaaaaaaa ["a", "aa", "aaa", "aaaa"..."aaaaaaaaaa"]. After reviewing the member function canBreak, may be it uses Greedy like method which will easily cause TLE for this problem, am I right? Waiting anyone give an idea. Thx.


  • 0
    B

    Agree. In canBreak(), you used greedy which causes the TLE. I think Trie is a good idea but definitely not necessary in this problem, because it could not improve the time/space time complexity. You can get same complexity through brutal force.


Log in to reply
 

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