Created
December 17, 2017 03:24
-
-
Save aquawj/e2dee40ac9d0dbae8787dd653f62efe5 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Design a data structure that supports the following two operations: | |
void addWord(word) | |
boolean search(word) | |
search(word) can search a literal word or a regular expression string containing only letters a-z or'.'means it can represent any one letter. | |
addWord("bad") | |
addWord("dad") | |
addWord("mad") | |
search("pad") -> false | |
search("bad") -> true | |
search(".ad") -> true | |
search("b..") -> true | |
//此题类似trie的实现,唯一在于点‘.’的处理。因为它可以代表任意字符,因此涉及到DFS处理 | |
class TrieNode{ | |
TrieNode[] children; | |
boolean isWord; | |
public TrieNode(){ | |
children = new TrieNode[26]; | |
isWord = false; | |
} | |
} | |
public class WordDictionary { | |
TrieNode root; | |
/** Initialize your data structure here. */ | |
public WordDictionary() { | |
root = new TrieNode(); | |
} | |
/** Adds a word into the data structure. */ | |
public void addWord(String word) { | |
TrieNode node = root; | |
for(int i = 0; i < word.length(); i++){ | |
int index = word.charAt(i) - 'a'; | |
if(node.children[index] == null){ | |
node.children[index] = new TrieNode(); | |
} | |
node = node.children[index]; | |
} | |
node.isWord = true; | |
} | |
/** 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 match(word.toCharArray(), 0, root); | |
} | |
public boolean match(char[] chs, int i, TrieNode node){ //从node往下找,匹配chs的从第i开始的字符 | |
if(i == chs.length){ | |
return node.isWord; | |
} | |
if(chs[i] != '.'){ //普通字母,返回 树中当前字母存在 && 从下一个下标找,从这个字母节点往下找,都匹配 | |
return node.children[chs[i] - 'a'] != null && match(chs, i + 1, node.children[chs[i] - 'a']); | |
}else{ //如果是".",看树中上一个node的所有children中,哪个字母是存在的,且这个字母之后的所有都匹配,只要找到一个就可以返回true | |
for(int j = 0; j < 26; j++){ | |
if(node.children[j] != null && match(chs, i + 1, node.children[j])){ | |
return true; | |
} | |
} | |
} | |
return false; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment