DFS+Trie solution MLE


  • 0
    G

    My submission shows that 43 test cases passed but got a MLE. Does anyone knows how to fix it?

    struct TrieNode
    {
    	bool flag;
    	TrieNode *childs[26];
    	TrieNode *parent;
    	TrieNode() :parent(NULL), flag(false) {
    		for (int i = 0; i < 26; i++)
    			childs[i] = NULL;
    	}
    };
    void insertWord(TrieNode *p, char* word)
    {
    	if ((*word)=='\0')
    	{
    		p->flag = true;
    		return;
    	}
    	int index = word[0] - 'a';
    	if (p->childs[index] == NULL)
    		p->childs[index] = new TrieNode();
    	if (p->childs[index]->parent == NULL)
    		p->childs[index]->parent = p;
    	insertWord(p->childs[index],word+1);
    }
    vector<int> getCanSplitPoints(TrieNode *p, char *s)
    {
    	int index;
    	vector<int> result;
    	int i = 0;
    	while ((*s)!='\0')
    	{
    		index = (*s) - 'a';
    		if (p->childs[index] != NULL)
    		{
    			if (p->childs[index]->flag) result.push_back(i);
    			p = p->childs[index];
    			i++;
    			s++;
    		}
    		else break;
    	}
    	return result;
    }
    bool search(TrieNode *p, char *s, int &count,set<string> &resultSet)
    {
    	if ((*s)=='\0') return true;
    	vector<int> points = getCanSplitPoints(p, s);
    	bool tmpflag;
    	if (points.size())
    	{
    		for (int i = 0; i < points.size(); i++)
    		{
    			count++;
    			string tmp = string(s + points[i] + 1);
    			if (resultSet.find(string(s + points[i] + 1)) != resultSet.end())
    				return true;
    			if (search(p,s+points[i] + 1, count,resultSet) && count>1)
    				return true;
    			count--;
    		}
    		return false;
    	}
    	return false;
    }
    class Solution {
    public:
    
    	vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
    		TrieNode *root = new TrieNode();
    		char* c = new char[2000];
    		for (int i = 0; i < words.size(); i++)
    		{
    			strcpy(c, words[i].c_str());
    			insertWord(root, c);
    		}
    		vector<string> result;
    		set<string> s;
    		int count;
    		for (int i = 0; i < words.size(); i++)
    		{
    			count = 0;
    			strcpy(c, words[i].c_str());
    			if (search(root, c, count,s) && words[i] != "")
    			{
    				result.push_back(words[i]);
    				s.insert(words[i]);
    			}
    		}
    		return result;
    	}
    };

  • 0
    S

    It's not a good idea to use raw pointer in c++,
    and I think you can improve your Trie Tree implement.


  • 0
    1

    You need to release memory and do other optimizations. I have opened another topic. You are welcomed to check if you are still interested.


Log in to reply
 

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