Pass in Custom Test case but fail in submission case


  • 0
    Y

    Hi admin,

    I copy paste and last test case into custom case text box and then test my following code. It works with around 250+ ms running time. And in the trie, only one char 'a' is added. So it should not cause MLE. But when I submitted the same code to OJ, it always failed in the last test case with MLE. Could you tell me why? Is it because custom case and submission case do not share the compiler or running environment? I use CPP. Looks like it is not the first time the CPP entry return interesting message to users.

    class TrieNode {
    public:
        char content;
        bool isEnd;
        unordered_map<char, TrieNode *> branches;
        
        TrieNode(char c=0, bool end=false){
            content = c;
            isEnd = end;
        }
    };
    
    class Trie{
    private:
        TrieNode *root;
    public:
        Trie(){
            root = new TrieNode();
        }
        
        void insert(string s){
            TrieNode *node = root;
            int i;
            for(i = 0; i < s.size(); ++ i){
                if(node->branches.find(s[i]) != node->branches.end()){
                    node = node->branches[s[i]];
                    if(i == s.size() - 1)
                        node->isEnd = true;
                }else
                    break;
            }
            for(; i < s.size(); ++ i){
                TrieNode *tmp = new TrieNode(s[i], i == s.size()-1?true:false);
                node->branches[s[i]] = tmp;
                node = tmp;
            }
        }
        
        void search(string &s, int start, vector<int> &dp){
            TrieNode *node = root;
            for(int i = start; i < s.size(); ++ i){
                if(node->branches.find(s[i]) != node->branches.end()){
                    node = node->branches[s[i]];
                    if(node->isEnd){
                        dp[i] = (start == 0? 1 : max(dp[i], dp[start - 1] + 1));
                    }
                }else
                    break;
            }
        }
    };
    
    class Solution {
    private:
        struct cmpfun{
            bool operator() (const string a, const string b){
                return a.size() < b.size();
            }
        }cmp;
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            vector<string> ans;
            if(words.size() == 0)
                return ans;
            sort(words.begin(), words.end(), cmp);
            Trie tree;
            int maxlen = 0;
            for(int i = 0; i < words.size(); ++ i){
                maxlen = max(maxlen, (int)words[i].size());
            }
            vector<int> dp(maxlen + 1);
            for(int i = 0; i < words.size(); ++ i){
                
                for(int j = 0; j < words[i].size(); ++ j)
                    dp[j] = 0;
                
                for(int j = 0; j < words[i].size(); ++ j){
                    if(j == 0 || dp[j - 1] > 0)
                        tree.search(words[i], j, dp);
                    if(dp[words[i].size() - 1] > 1){
                        ans.push_back(words[i]);
                        break;
                    }
                }
                //output the index of word that will be added to Trie
                if(dp[words[i].size() - 1] <= 1){
                    printf("i = %d\n",i);
                    tree.insert(words[i]);
                }
            }
            return ans;
        }
    };
    

    0_1482692657260_Screen Shot 2016-12-25 at 11.03.42 AM.png


Log in to reply
 

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