[LeetCode]Concatenated Words

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



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