前缀树
# 208. 实现 Trie (前缀树) (opens new window)
class Trie {
class TrieNode{
boolean isWord;
TrieNode[] children;
public TrieNode(){
this.isWord = false;
this.children = new TrieNode[26];
}
}
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode cur = root;
for(int i=0;i<word.length();i++){
int c = word.charAt(i)-'a';
if(cur.children[c]==null)
cur.children[c] = new TrieNode();
cur = cur.children[c];
}
cur.isWord = true;
}
public boolean search(String word) {
TrieNode cur = root;
for(int i=0;i<word.length();i++){
int c = word.charAt(i)-'a';
if(cur.children[c]==null)
return false;
cur = cur.children[c];
}
return cur.isWord;
}
public boolean startsWith(String prefix) {
TrieNode cur = root;
for(int i=0;i<prefix.length();i++){
int c = prefix.charAt(i)-'a';
if(cur.children[c]==null)
return false;
cur = cur.children[c];
}
return true;
}
}
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
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
# 211. 添加与搜索单词 (opens new window)
class WordDictionary {
class TrieNode{
boolean isEnd;
TrieNode[] children;
public TrieNode(){
isEnd = false;
children = new TrieNode[26];
}
}
TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
public void addWord(String word) {
TrieNode cur = root;
for(int i=0;i<word.length();i++){
int c = word.charAt(i)-'a';
if(cur.children[c]==null){
cur.children[c] = new TrieNode();
}
cur = cur.children[c];
}
cur.isEnd = true;
}
public boolean search(String word) {
return search(root,word,0);
}
boolean search(TrieNode cur,String word,int start){
int n = word.length();
if(start == n){
return cur.isEnd;
}
char c = word.charAt(start);
if(c!='.'){
TrieNode child = cur.children[c-'a'];
return child!=null && search(child,word,start+1);
}
for(int i=0;i<26;i++){
if(cur.children[i]!=null && search(cur.children[i],word,start+1)){
return true;
}
}
return false;
}
}
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
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
# 386. 字典序排数 (opens new window)
前缀树：
class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>();
int cur = 1;
for(int i=0;i<n;i++){
res.add(cur);
if(cur * 10<=n){
cur *= 10;
}else{
// 枚举到当前前缀的最深处了，需要回到上一层并到下一个同层节点
while(cur%10==9 || cur>=n){
cur /= 10;
}
cur++;
}
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
回溯：
class Solution {
List<Integer>res = new ArrayList<>();
public List<Integer> lexicalOrder(int n) {
for(int i=1;i<=9;i++){
dfs(i,n);
}
return res;
}
void dfs(int cur,int limit){
if(cur>limit)return ;
res.add(cur);
for(int i=0;i<=9;i++){
dfs(cur*10+i,limit);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16