Screenshot from 2016-03-02 00:15:09.png
My code:
public class WordDictionary {
private class TrieNode {
char c;
boolean isLeaf;
HashMap<Character, TrieNode> tracker = new HashMap<Character, TrieNode>();
TrieNode() {
}
}
private TrieNode root = new TrieNode();
// Adds a word into the data structure.
public void addWord(String word) {
if (word == null || word.length() == 0)
return;
TrieNode temp = root;
for (int i = 0; i < word.length(); i++) {
char curr = word.charAt(i);
if (temp.tracker.containsKey(curr)) {
temp = temp.tracker.get(curr);
}
else {
TrieNode newNode = new TrieNode();
newNode.c = curr;
temp.tracker.put(curr, newNode);
temp = newNode;
}
if (i == word.length() - 1)
temp.isLeaf = 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) {
if (word == null || word.length() == 0)
return false;
return search(word, 0, root);
}
private boolean search(String word, int p, TrieNode t) {
if (p >= word.length())
return t.isLeaf;
TrieNode temp = t;
boolean ret = false;
for (int i = p; i < word.length(); i++) {
char curr = word.charAt(i);
if (curr == '.') {
for (Character c : temp.tracker.keySet()) {
TrieNode next = temp.tracker.get(c);
ret = ret | search(word,i + 1, next);
if (ret)
return ret;
}
return false;
}
else {
if (!temp.tracker.containsKey(curr))
return false;
else {
temp = temp.tracker.get(curr);
}
}
}
return temp.isLeaf;
}
}
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");
自己写了出来。
主要一个地方是，
"." 的时候，需要多个入口dfs，那么，只要有一个dfs成功了，后面的就不需要继续进行了，直接return。这样才能不超时。
Anyway, Good luck, Richardo!
My code:
public class WordDictionary {
private TrieNode root = new TrieNode('-');
private class TrieNode {
boolean isWord = false;
HashMap<Character, TrieNode> table;
char val;
TrieNode(char input) {
val = input;
table = new HashMap<Character, TrieNode>();
}
}
// Adds a word into the data structure.
public void addWord(String word) {
if (word == null || word.length() == 0) {
return;
}
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char curr = word.charAt(i);
if (node.table.containsKey(curr)) {
node = node.table.get(curr);
}
else {
TrieNode newTrieNode = new TrieNode(curr);
node.table.put(curr, newTrieNode);
node = newTrieNode;
}
}
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) {
if (word == null || word.length() == 0) {
return false;
}
return search(word, root, 0);
}
private boolean search(String word, TrieNode node, int index) {
if (index >= word.length()) {
return node.isWord;
}
char curr = word.charAt(index);
if (node.table.containsKey(curr)) {
node = node.table.get(curr);
return search(word, node, index + 1);
}
else if (curr == '.') {
boolean flag = false;
Set<Character> set = node.table.keySet();
for (Character c : set) {
flag = flag | search(word, node.table.get(c), index + 1);
if (flag) {
return true;
}
}
return false;
}
else {
return false;
}
}
}
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");
这道题目的思想和以前差不多。一开始没做出来。
另外可以用 array来代替 hashmap
另外：
java hashset iterator performance
hashmap .keySet() O(1)
for (Character c : set) {...} O(n) n = backup array length
遍历的时候，仍然要遍历整个数组，如果为空，就跳过。
Anyway, Good luck, Richardo! -- 08/19/2016
