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
131
132
133
134
135
136
137
138
| import java.util.*;
public class Main {
/*请完成下面这个函数，实现题目要求的功能*/
/*当然，你也可以不按照下面这个模板来作答，完全按照自己的想法来 ^-^ */
/******************************开始写代码******************************/
static class Node{
Node[] nodes = new Node[256];
boolean isWord = false;
}
public String[] doFilter(String[] source, String filter) {
// 构造单词树
Node root = new Node();
Node tmp = root;
for(String string : source) {
for(int i = 0; i < string.length(); i++) {
if(tmp.nodes[string.charAt(i) + 0] == null) {
tmp.nodes[string.charAt(i) + 0] = new Node();
}
tmp = tmp.nodes[string.charAt(i) + 0];
}
tmp.isWord = true;
tmp = root;
}
ArrayList<String> result = new ArrayList<>(); // 保存满足条件的字符串
findRes(result, 0, filter, root, "");
int L = result.size();
String[] strings = new String[L];
for(int i = 0; i < L; i++) {
strings[i] = result.get(i);
}
return strings;
}
/**
*
* @param list
* @param index:当前root需要找的下一个filter字符下标
* @param filter
* @param root
* @param string
*/
public void findRes(ArrayList<String> list, int index ,String filter, Node root, String string) {
if(index == filter.length()) { // 找到匹配
if(root.isWord) {
list.add(string); // 是单词，加入结果集
}
deepFind(list, root, string); // 全部匹配后继续向下搜索符合要求的单词
return;
}
char c = filter.charAt(index);
if(root.nodes[c+0] != null) { // 优先匹配当前字符
Node before = root; // 递归返回时保证依然能找到当前节点
root = root.nodes[c+0];
string = string + c;
findRes(list, index+1, filter, root, string);
string = string.substring(0, string.length()-1);
root = before;
}
for(int k = 0; k < 256; k++) {
if(k == c+0) { // 避免重复搜索
continue;
}
if(root.nodes[k+0] != null) {
Node before = root; // 递归返回时保证依然能找到当前节点
root = root.nodes[k+0];
string = string + (char)k;
findRes(list, index, filter, root, string);
string = string.substring(0, string.length()-1);
root = before;
}
}
}
public void deepFind(ArrayList<String> list, Node root, String string) {
for(int k = 0; k < 256; k++) {
if(root.nodes[k] != null) {
Node before = root; // 递归返回时保证依然能找到当前节点
root = root.nodes[k];
string = string + (char)k;
if(root.isWord) {
list.add(string);
}
deepFind(list, root, string);
string = string.substring(0, string.length()-1);
root = before;
}
}
}
/******************************结束写代码******************************/
public static void main(String[] args){
String[] _source = {
"AB",
"ABC",
"ACB",
"ABCD",
"ADBCF",
"ABDCF",
"ABDC",
"ABDFCG",
"ABDFGC",
"ABDEFG",
"GABCEFG"
};
Scanner in = new Scanner(System.in);
ArrayList<String> _filter = new ArrayList<>();
while(in.hasNext()) {
_filter.add(in.nextLine());
}
Main main = new Main();
for(int i = 0; i < _filter.size(); i++) {
String[] res = main.doFilter(_source, _filter.get(i));
if(res.length == 0) {
System.out.println(-1);
}else {
for(int res_i=0; res_i < res.length; res_i++) {
System.out.println(String.valueOf(res[res_i]));
}
}
}
}
}
|