FilesExpand file tree

 master

/

WordDictionary.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

58 lines (51 loc) · 1.65 KB

 master

/

WordDictionary.java

Copy path

Top

File metadata and controls

• Code
• Blame

58 lines (51 loc) · 1.65 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

public class WordDictionary {

private class Trie {

Trie[] nodes = new Trie[26];

String word;

}

Trie root = new Trie();

// Adds a word into the data structure.

public void addWord(String word) {

Trie node = root;

for (char c : word.toCharArray()) {

if (node.nodes[c - 'a'] == null) {

node.nodes[c - 'a'] = new Trie();

}

node = node.nodes[c - 'a'];

}

node.word = word;

}

// Returns if the word is in the data structure. A word could

// contain the dot character '.' to represent any one letter.

public boolean search(String word) {

return search(root, word, 0);

}

private boolean search(Trie trie, String word, int index) {

if (trie == null) {

return false;

}

if (index == word.length()) {

/**

* 这个返回的条件一定要注意，不是trie.word.equals(word)，因为word中可能带'.'

*/

return trie.word != null;

}

char c = word.charAt(index);

if (c != '.') {

return search(trie.nodes[c - 'a'], word, index + 1);

} else {

for (Trie node : trie.nodes) {

if (node != null) {

if (search(node, word, index + 1)) {

return true;

}

}

}

return false;

}

}

}

// Your WordDictionary object will be instantiated and called as such:

// WordDictionary wordDictionary = new WordDictionary();

// wordDictionary.addWord("word");

// wordDictionary.search("pattern");