Concatenated Words
给一个字符串组, 返回所有在里面的由两个以上字符串拼接组成的字符串. 这个题主要考察剪枝, 首先要查重, 用一个set重新装一下数组, 然后按照字典序排序, 然后逐个看是不是答案, 验证的时候, 每个substring都要看一下, 用一个dp当memo, 记录已经看过的字符串.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
public class Solution { public List<String> findAllConcatenatedWordsInADict(String[] words) { List<String> result = new ArrayList<>(); Set<String> preWords = new HashSet<>(); Arrays.sort(words, new Comparator<String>() { public int compare (String s1, String s2) { return s1.length() - s2.length(); } }); for(int i = 0 ; i < words.length; i++) { if(canForm(words[i],preWords)) result.add(words[i]); preWords.add(words[i]); } return result; } public boolean canForm(String word, Set<String> dict) { boolean[] dp = new boolean[word.length() + 1]; dp[0] = true; if(dict.isEmpty()) return false; for(int i = 1; i <= word.length(); i++) { for(int j = 0 ; j < i; j++){ if(dp[j]&&dict.contains(word.substring(j,i))){ dp[i] = true; break; } } } return dp[word.length()]; } } |