Easy C++ dfs and AC trie solution


  • 0
    1. easy dfs could solve this.
    class Solution
    {
    private:
    	unordered_set<string> dict;
    	bool dfs(string word, int count)
    	{
    		if (word.empty())
    			return count > 1;
    		string::size_type n = word.length();
    		for (int i = 1; i <= n; ++i)
    			if (dict.count(word.substr(0, i)) && dfs(word.substr(i), count + 1))
    				return true;
    		return false;
    	}
    public:
    	vector<string> findAllConcatenatedWordsInADict(vector<string>& words)
    	{
    		vector<string> res;
    		sort(words.begin(), words.end(),
    			[](const string &lhs, const string &rhs) { return lhs.length() < rhs.length(); });
    		for (auto &word : words)
    		{
    			if (dfs(word, 0))
    				res.push_back(word);
    			else
    				dict.insert(word);
    		}
    		return res;
    	}
    };
    
    1. thanks to @1069450252-qq-com 's idea that using stack to allocate memory instead of heap in case of MLE.
      My AC 192ms trie code:
    struct TrieNode;
    TrieNode *pool[54000][26];
    typedef struct TrieNode
    {
    	int index;
    	bool isStr;
    	TrieNode **next = nullptr;
    	TrieNode(int id) : index(id), isStr(false) 
    	{
    		// reset to null because last run may polluted the pool
    		memset(pool[index], 0, sizeof(pool[index]));
    		next = pool[index];
    	}
    }Trie;
    class Solution
    {
    private:
    	void insert(string s)
    	{
    		if (!root || s.empty()) return;
    		TrieNode *curr = root;
    		for (int i = 0; i < s.length(); ++i)
    		{
    			int pos = s[i] - 'a';
    			if (curr->next[pos] == nullptr)
    				curr->next[pos] = new TrieNode(identity++);
    			curr = curr->next[pos];
    		}
    		curr->isStr = true;
    	}
    	bool dfs(const string &s, int start)
    	{
    		TrieNode *curr = root;
    		auto it = start;
    		while (curr && it != s.length())
    		{
    			if (curr->isStr && dfs(s, it))
    				return true;
    			if (curr->next[s[it] - 'a'] == nullptr)
    				return false;
    			curr = curr->next[s[it++] - 'a'];
    		}
    		if (curr->isStr)
    			return true;
    		return false;
    	}
    	Trie *root = nullptr;
    	int identity = 0;
    public:
    	vector<string> findAllConcatenatedWordsInADict(vector<string>& words)
    	{
    		vector<string> res;
    		if (words.empty()) return res;
    		identity = 0;
    		root = new TrieNode(identity++);
    		sort(words.begin(), words.end(), [](const string &lhs, const string &rhs) { return lhs.length() < rhs.length(); });
    		for (auto &s : words)
    		{
    			if (dfs(s, 0))
    				res.push_back(s);
    			else
    				insert(s);
    		}
    		return res;
    	}
    };
    

Log in to reply
 

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