Given a dictionary of strings [ strings are in sorted order] find the precedence of characters according to the dictionary..

http://www.careercup.com/question?id=13394663

给你一个按字母顺序排好的字典(但你不知道字母顺序,非英语),要求找出字母顺序
例:
单词顺序:
wrt
wrf
er
ett
rftt
字母顺序:
w,e,r,t,f

首先建DAG。
然后TOPOLOGICAL SORT。

建立DAG的时候可以用3-WAY SORT 优化。
3 way sort的好处就是减少字母与字母之间的比较

比如bf的话,就两两得挨个字符比较
但是比如 aaaaab aaaaac aaaaad
bf就是aaaaab 和aaaaac 先比较之后aaaaac 和 aaaaad比较,但如果先首尾,aaaaab和aaaaac比较的话,就知道这两个之间的string前面5个字符都是相同的了,就可以减少亮亮之间的比较

public void threeWaySort(String[] words, int start, int end, int idx, HashMap<Character,HashSet> map){
if(start>=words.length || start>=end) return;
String startStr = words[start], endStr=words[end];
if(startStr.length()<=idx || endStr.length()<=idx) return;
Character sChar = startStr.charAt(idx),eChar=endStr.charAt(idx);
if(sChar==eChar){
threeWaySort(words,start,end,idx+1,map);
} else{
if(!map.containsKey(eChar)){
HashSet set = new HashSet();
set.add(sChar);
map.put(eChar,set);
} else{
map.get(eChar).add(sChar);
}
int mid = start +(end-start)>>1;
threeWaySort(words,start,mid,idx,map);
threeWaySort(words,mid+1,end,idx,map);
}
}
public void topSort(HashMap<Character,HashSet> map, ArrayList sorted, Character ch,HashSet used){
if(used.contains(ch)) return;
used.add(ch);
for(Character c : map.get(ch)){
topSort(map,sorted,c,used);
}
sorted.add(ch);
}

public ArrayList sortLetters(String[] words){

Map<Character,HashSet> map =new HashMap<Character,HashSet>();

threeWaySort(words,0,words.length-1,0,map);

ArrayList sorted=new ArrayList();

HashSet used = new HashSet();

for(Character ch : map.keySet())

topSort(map,sorted,ch,used);

return sorted;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s