[LeetCode]Concatenated Words

这道题和Word Break很像，我们只需要将Word Break的做法扩展一下即可。我们将words按照从短到长sort，依次加入字典并且看当前word能否break成字典里的组合，因为当前word只能break成更短的word的组合，我们先check能否break再插入字典，这样就避免自己组合成自己的情况。假设输入n个字符，每个string平均长度m，时间复杂度O(n * m^2)，代码如下：

	class Solution {
	public:
	vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
	int len = words.size();
	auto comp = [](const string& lhs, const string& rhs){return lhs.size() < rhs.size();};
	sort(words.begin(), words.end(), comp);
	unordered_set<string> dict;
	vector<string> res;
	for(auto&& word : words)
	{
	if(canBreak(word, dict)){res.push_back(word);};
	dict.insert(word);
	}
	return res;
	}
	private:
	bool canBreak(string& str, unordered_set<string>& dict)
	{
	if(dict.empty())return false;
	int len = str.size();
	vector<bool> dp(len + 1, false);
	dp[0] = true;
	for(int i = 0; i < len; ++i)
	{
	for(int j = 0; j <= i; ++j)
	{
	if(dp[j] && dict.find(str.substr(j, i - j + 1)) != dict.end())
	{
	dp[i + 1] = true;
	break;
	}
	}
	}
	return dp[len];
	}
	};

view raw Concatenated Words_dp.cpp hosted with ❤ by GitHub

还有一种解法是DFS，也就是找到有没有一种break的可能。这里我们不用hashmap，用trie，因为trie可以帮助我们更好地剪枝，因为我们一旦发现当前prefix不存在字典当中就可以break了，因为prefix不存在的话更不可能存在以prefix开头的word了，而hashmap我们还需要遍历后面的字符。代码如下：

	struct Node
	{
	bool isLeaf;
	unordered_map<char, Node*> children;
	Node() : isLeaf(false)
	{
	}
	};
	class Solution {
	public:
	Solution() : m_root(new Node())
	{
	}
	~Solution()
	{
	garbageCollect(m_root);
	}
	vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
	vector<string> res;
	auto comp = [](const string& lhs, const string& rhs){return lhs.size() < rhs.size();};
	sort(words.begin(), words.end(), comp);
	for(auto&& word : words)
	{
	if(word.empty())continue;
	if(tryBreak(word)){res.push_back(word); continue;}
	insert(word);
	}
	return res;
	}
	private:
	Node* m_root;
	void insert(string word)
	{
	int len = word.size(), i = 0;
	auto curr = m_root;
	for(int i = 0; i < len; ++i)
	{
	if(!curr->children[word[i]])
	curr->children[word[i]] = new Node();
	curr = curr->children[word[i]];
	}
	curr->isLeaf = true;
	}
	bool tryBreak(string word)
	{
	if(word.empty())return true;
	auto curr = m_root;
	int i = 0;
	while(curr && i <= word.size())
	{
	if(curr->isLeaf && tryBreak(word.substr(i)))
	return true;
	curr = curr->children[word[i++]];
	}
	return false;
	}
	void garbageCollect(Node* curr)
	{
	if(!curr)return;
	for(auto child : curr->children)
	garbageCollect(child.second);
	delete curr;
	}
	};

view raw Concatenated Words_dfs+trie.cpp hosted with ❤ by GitHub