Alien Dictionary

Leave a comment

December 19, 2016 by oneOokay

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example,
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Note:

  1. You may assume all letters are in lowercase.
  2. If the order is invalid, return an empty string.
  3. There may be multiple valid order of letters, return any one of them is fine.

所以是到了被corner case折磨到死的阶段了吗=。=

首先敲黑板仔细审题!这个跟前面google那个sequence-reconstruction类似但是不一样:

sequence-reconstruction是根据一个input array:int[][]来进行拓扑排序,他们的拓扑顺序是由input中的一个单独int[]来确定的,不同int[]之间并不存在拓扑关系(即交换int[]在input中出现的顺序的话并不会影响最终的拓扑排序。

而这个题目!!!是字典啊同学们!字典本身就是一个很tricky的东西。input是一个String[]: 交换里头元素的顺序是会影响排序的,因为是字典。。。

  • input里面出现的每一个char都应该要出现在最终的ans里面(if valid)
  • 前后两个词之间的关系定义拓扑关系:第一个在相同index上出现的不同的char,形成了一个拓扑关系;而且只有第一个,再次出现在相同index上不同的char就没有拓扑意义了
  • invalid的判断:首先要是一个valid DAG(result.length() == degree.size()); 其次要是一个valid的字典:corner case:“wrtkj” “wrt”就不是一个valid的字典。
  • 下面的代码是一个优化的代码:
    • 先初始化indegrees map
    • graph Map用Set,而不是用ArrayList,避免了重复处理
    • 因为没有对graph进行初始化,所以要注意判断if(graph.containsKey)
  • str.length()
public String alienOrder(String[] words) {
        if(words == null || words.length == 0){
            return "";
        }
//用Set避免重复处理
        HashMap<Character, Set<Character>> graph = new HashMap<>();
        HashMap<Character, Integer> indegrees  = new HashMap<>();
        for(String word : words){
            for (char c : word.toCharArray()){
                indegrees.put(c, 0); //在这里仅初始化indegrees,并不初始化graph
            }
        }
        
        for (int i = 0; i < words.length - 1; i ++){
            String first = words[i];
            String second = words[i + 1];
            for(int j = 0; j < Math.min(first.length(), second.length()); j ++){
                char fc = first.charAt(j);
                char sc = second.charAt(j);
//只有当两个char不等的时候,才会产生一个graph里面的对应关系
                if (fc != sc){
//这里就处理了之前没有对graph进行初始化的情况
                    Set<Character> set = new HashSet<>();
                    if (graph.containsKey(fc))
                        set = graph.get(fc);
                    if (!set.contains(sc)){
                        set.add(sc);
                        graph.put(fc, set);
                        indegrees.put(sc, indegrees.get(sc) + 1);
                    }
                    break;
                }else //invalid corner case:"abcd", "ab"
//走到了一个词的最后一个c还没有break,说明之前的字符都是相同的;以下的if则说明了second
其实是first的一个prefix,first长于second,这种情况是invalid
               if(j + 1 <= first.length() - 1 
                && j + 1 == second.length()) 
                  return "";
            }
        }
        
        Queue<Character> queue = new LinkedList<>();
        for (char c : indegrees.keySet()){
            if (indegrees.get(c) == 0){
                queue.offer(c);
            }
        }
        String ans = "";
        while (!queue.isEmpty()){
            char cur = queue.poll();
            ans += cur;
            if (graph.containsKey(cur)){//这也是对之前没有初始化graph的check
               Set next = graph.get(cur);
                for(char c : next){
                    indegrees.put(c, indegrees.get(c) - 1);
                    if (indegrees.get(c) == 0){
                        queue.offer(c);
                    }
                } 
            }
        }
//对graph是否是valid DAG(Directed Acrylic Graph)的判断
        if (ans.length() != indegrees.size()) return "";
        return ans;
    }
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

%d bloggers like this: