LeetCode link

first thought

  • create a set to maintain all the words
  • split each word from index i (i from 0 to end), if the first part of it is in the set, and split the second recursively.
  • remember each word should be split at least once.

solution

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
public class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> set = new HashSet<>();
        for (String word: words) {
            if (word.length() > 0) {
                set.add(word);
            }
        }
        List<String> results = new ArrayList<>();
        for (String word: words) {
            if (word.length() > 0) {
                this.helper(word, set, 0, results);
            }
        }
        return results;
    }
    private void helper(String word, Set<String> set, int start, List<String> results) {
        if (start == word.length()) {
            results.add(word);
        }
        for (int i = start + 1; i <= word.length(); i++) {
            String first = word.substring(start, i);
            if (set.contains(first) && !first.equals(word)) {
                this.helper(word, set, i, results);
            }
        }
    }
}

problem

has duplicated output

reason

a valid word may be added to the results for more than once because the different split during recursion.(e.g input: [a,b,ab,aa,aab] so ‘aab’ is split to ‘a ab’ and ‘aa b’ are both ok)

modification

change the results from List to Set

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
public class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> set = new HashSet<>();
        for (String word: words) {
            if (word.length() > 0) {
                set.add(word);
            }
        }
        Set<String> results = new HashSet<>();
        for (String word: words) {
            if (word.length() > 0) {
                this.helper(word, set, 0, results);
            }
        }
        List<String> result = new ArrayList<>();
        result.addAll(results);
        return result;
    }
    private void helper(String word, Set<String> set, int start, Set<String> results) {
        if (start == word.length()) {
            results.add(word);
        }
        for (int i = start + 1; i <= word.length(); i++) {
            String first = word.substring(start, i);
            if (set.contains(first) && !first.equals(word)) {
                this.helper(word, set, i, results);
            }
        }
    }
}

problem

TLE

reason

the same as the previous problem, check one word for several times

modification

if a word is valid, then jump out of the recursion and continue to check the next one.And this can also fix the first duplicate problem.

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
public class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> set = new HashSet<>();
        for (String word: words) {
            if (word.length() > 0) {
                set.add(word);
            }
        }
        List<String> results = new ArrayList<>();
        for (String word: words) {
            if (word.length() > 0 && this.helper(word, set, 0)) {
                results.add(word);
            }
        }
        return results;
    }
    private boolean helper(String word, Set<String> set, int start) {
        if (start == word.length()) {
            return true;
        }
        for (int i = start + 1; i <= word.length(); i++) {
            String first = word.substring(start, i);
            if (set.contains(first) && !first.equals(word)) {
                if (this.helper(word, set, i)) {
                    return true;
                }
            }
        }
        return false;
    }
}