-
Notifications
You must be signed in to change notification settings - Fork 53
Expand file tree
/
Copy pathLeetCode_211_9.java
More file actions
130 lines (109 loc) · 3.44 KB
/
LeetCode_211_9.java
File metadata and controls
130 lines (109 loc) · 3.44 KB
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
package com.github.lifelab.leetcode.problemset;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.regex.Pattern;
/**
* 添加与搜索单词 - 数据结构设计 @see https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/
*
* @author Weichao Li (liweichao0102@gmail.com)
* @since 2019-06-30
*/
public class Solution211 {
/**
* hash + cache 实现
*/
public class WordDictionary1 {
private Map<String, String> wd;
private Map<String, Boolean> cache;
/**
* Initialize your data structure here.
*/
public WordDictionary1() {
this.wd = new HashMap<>();
this.cache = new HashMap<>();
}
/**
* Adds a word into the data structure.
*/
public void addWord(String word) {
wd.put(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) {
Boolean cacheValue = cache.get(word);
if (Objects.nonNull(cacheValue) && cacheValue) {
return cacheValue;
} else {
cacheValue = wd.keySet().parallelStream().anyMatch(e -> Pattern.matches(word, e));
cache.put(word, cacheValue);
}
return cacheValue;
}
}
/**
* tree 实现
*/
public class WordDictionary2 {
class Node {
private Node[] next;
private boolean isWord;
public Node() {
next = new Node[26];
isWord = false;
}
}
private Node root;
/**
* Initialize your data structure here.
*/
public WordDictionary2() {
root = new Node();
}
/**
* Adds a word into the data structure.
*/
public void addWord(String word) {
int len = word.length();
Node curNode = root;
for (int i = 0; i < len; i++) {
char curChar = word.charAt(i);
Node next = curNode.next[curChar - 'a'];
if (next == null) {
curNode.next[curChar - 'a'] = new Node();
}
curNode = curNode.next[curChar - 'a'];
}
if (!curNode.isWord) {
curNode.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, root, 0);
}
private boolean match(String word, Node node, int start) {
if (start == word.length()) {
return node.isWord;
}
char alpha = word.charAt(start);
if (alpha == '.') {
for (int i = 0; i < 26; i++) {
if (node.next[i] != null && match(word, node.next[i], start + 1)) {
return true;
}
}
return false;
} else {
if (node.next[alpha - 'a'] == null) {
return false;
}
return match(word, node.next[alpha - 'a'], start + 1);
}
}
}
}