public class Solution {
class TrieNode{
TrieNode[] children;
int count;
boolean isEnd;
public TrieNode(){
count = 0;
children = new TrieNode[256];
}
}
public String kCommonPrefix(String[] strs, int k) {
TrieNode root = new TrieNode();
Stack<Character> path = new Stack<>();
int max = k;
for(int j = 0; j < strs.length; j++){
String s = strs[j];
TrieNode cur = root;
Stack<Character> tmp = new Stack<>();
for(int i = 0; i < s.length(); i++){
int x = s.charAt(i);
if(cur.children[x] == null){
cur.children[x] = new TrieNode();
}
cur.children[x].count++;
cur = cur.children[x];
if(cur.count >= max){
tmp.push(s.charAt(i));
max = cur.count;
}
}
if(tmp.size() > path.size()){
path = new Stack<>();
while(!tmp.empty()) path.push(tmp.pop());
}
}
StringBuilder sb = new StringBuilder();
while(!path.empty()){
sb.append(path.pop());
}
return sb.toString();
}
}
2016年10月7日星期五
Prefix that appears at least k times
given an array of strings and int k, find the prefix that appears at least k times.
订阅:
博文评论 (Atom)
没有评论:
发表评论