Leetcode Concatenated Words
472. Concatenated Words
Given a list of words, 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:
|
1 2 3 4 5 6 7 8 |
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.
|
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
public class Solution { public List<String> findAllConcatenatedWordsInADict(String[] words) { int min = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE; int max = 0; Set<String> set = new HashSet<>(); for(String word: words) { int len = word.length(); if(len <= min) { secondMin = min; min = len; } else if(len < secondMin) { secondMin = len; } max = Math.max(max, len); set.add(word); } List<String> res = new ArrayList<>(); int minLen = min + min; for(String w: words) { int len = w.length(); if(len < minLen) continue; if(test(w, 0, set, min, max, 0)) { res.add(w); } } return res; } boolean test(String w, int start, Set<String> words, int min, int max, int cnt) { if(start == w.length()) { if(cnt > 1) return true; return false; } for(int i = min; i < max; i++) { if(start + i > w.length()) break; String tmp = w.substring(start, start + i); if(words.contains(tmp)) { if(test(w, start + i, words, min, max, cnt + 1)) { return true; } } } return false; } } |
