FilesExpand file tree

 master

/

ConcatenatedWords472.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

76 lines (69 loc) · 2.43 KB

 master

/

ConcatenatedWords472.java

Copy path

Top

File metadata and controls

• Code
• Blame

76 lines (69 loc) · 2.43 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

/**

* 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.

*/

public class ConcatenatedWords472 {

public List<String> findAllConcatenatedWordsInADict(String[] words) {

Trie trie = constructTrie(words);

List<String> res = new ArrayList<>();

for (String word: words) {

if (count(trie, word.toCharArray(), 0, trie, 1) >= 2) {

res.add(word);

}

}

return res;

}

private int count(Trie trie, char[] chars, int i, Trie root, int cnt) {

if (i == chars.length) return -1;

int idx = chars[i] - 'a';

if (trie.children[idx] == null) return -1;

if (trie.children[idx].isWord) {

if (i == chars.length - 1) return cnt;

int tmp = count(root, chars, i+1, root, cnt+1);

if (tmp >= 2) {

return tmp;

}

}

return count(trie.children[idx], chars, i+1, root, cnt);

}

private Trie constructTrie(String[] words) {

Trie trie = new Trie();

for (String word: words) trie.add(word);

return trie;

}

class Trie {

Trie[] children = new Trie[26];

boolean isWord;

void add(String word) {

add(word.toCharArray(), 0);

}

void add(char[] chars, int i) {

if (i == chars.length) {

isWord = true;

return;

}

int idx = chars[i] - 'a';

if (children[idx] == null) {

children[idx] = new Trie();

}

children[idx].add(chars, i+1);

}

}

}