472. Concatenated Words

472. Concatenated Words

Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example:

Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

Note: The number of elements of the given array will not exceed 10,000 The length sum of elements in the given array will not exceed 600,000. All the input string will only include lower case letters. The returned elements order does not matter.

思路： 从list中找出所有字符串，该字符串至少由list中的两个单词构成。 我们首先按字符串长度由小到大排列words. 然后构造一个set, 依次加入set中。对于具体的字符串word，如果word可以由至少set中的两个word构成，则该word加入结果集中。这种字符串的prefix问题，很明显要用dynamic programming来解。

class Solution { public List findAllConcatenatedWordsInADict(String[] words) { List res = new ArrayList<>(); if (words==null || words.length==0) return res; HashSet dict = new HashSet<>(); Arrays.sort(words, new Comparator() { public int compare(String str1, String str2) { return str1.length() - str2.length(); } }); for (String word : words) { if (canForm(word, dict)) res.add(word); dict.add(word); } return res; } public boolean canForm(String word, HashSet dict) { if (dict.isEmpty()) return false; boolean[] dp = new boolean[word.length()+1]; dp[0] = true; for (int i=1; i<=word.length(); i++) { for (int j=0; j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。