-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_14.java
More file actions
48 lines (43 loc) · 1.34 KB
/
Copy pathP_14.java
File metadata and controls
48 lines (43 loc) · 1.34 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
package leetcode.easy;
public class P_14 {
static class Trie {
Trie[] children = new Trie[26];
char firstChar = '*';
int size = 1;
}
public String longestCommonPrefixTrie(String[] strings) {
final Trie root = new Trie();
for (String w : strings) {
Trie iter = root;
for (char c : w.toCharArray()) {
if (iter.firstChar == c) {
iter.size++;
}
iter.firstChar = c;
if (iter.children[c - 'a'] == null) {
iter.children[c - 'a'] = new Trie();
}
iter = iter.children[c - 'a'];
}
}
final StringBuilder sb = new StringBuilder();
Trie iter = root;
while (iter.firstChar != '*' && iter.size == strings.length) {
sb.append(iter.firstChar);
iter = iter.children[iter.firstChar - 'a'];
}
return sb.toString();
}
public String longestCommonPrefix(String[] strings) {
if (strings.length == 0) {
return "";
}
String pre = strings[0];
for (int i = 1; i < strings.length; i++) {
while (!strings[i].startsWith(pre)) {
pre = pre.substring(0, pre.length() - 1);
}
}
return pre;
}
}