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.


 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();  
   }  
 }  

没有评论:

发表评论