Concatenated Words LeetCode solution in Java

1
class Solution {
2
  public List<String> findAllConcatenatedWordsInADict(String[] words) {
3
    // sort the array in asc order of word length, since longer words are formed by shorter words.
4
    Arrays.sort(words, (a, b) -> a.length() - b.length());
5

6
    List<String> result = new ArrayList<>();
7

8
    // list of shorter words
9
    HashSet<String> preWords = new HashSet<>();
10

11
    for (int i = 0; i < words.length; i++) {
12
      // Word Break-I problem.
13
      if (topDown(words[i], preWords, 0, new Boolean[words[i].length()])) {
14
        result.add(words[i]);
15
      }
16
      preWords.add(words[i]);
17
    }
18
    return result;
19
  }
20

21
  private boolean topDown(String s, HashSet<String> wordDict, int startIndex, Boolean[] memo) {
22
    if (wordDict.isEmpty()) {
23
      return false;
24
    }
25
    // if we reach the beyond the string, then return true
26
    // s = "leetcode" when "code" is being checked in the IF() of the loop, we reach endIndex ==
27
    // s.length(),
28
    // and wordDict.contains("code") => true and topDown(s, wordDict, endIndex, memo) needs to
29
    // return true.
30
    if (startIndex == s.length()) {
31
      return true;
32
    }
33

34
    // memo[i] = true means => that the substring from index i can be segmented.
35
    // memo[startIndex] means => wordDict contains substring from startIndex and it can be
36
    // segemented.
37
    if (memo[startIndex] != null) { // Boolean[] array's default value is "null"
38
      return memo[startIndex];
39
    }
40

41
    for (int endIndex = startIndex + 1; endIndex <= s.length(); endIndex++) {
42
      if (wordDict.contains(s.substring(startIndex, endIndex))
43
          && topDown(s, wordDict, endIndex, memo)) {
44
        memo[startIndex] = true;
45
        return true;
46
      }
47
    }
48
    memo[startIndex] = false;
49
    return false;
50
  }
51
}