Alien Dictionary

Problem

Alien Dictionary

Approach

we can infer the new rules about these characters firstly. And then with the rules, it’s easy to pick up the smallest char. Topological sort method works for this.

Code

public class Solution {
    private void compareString(String a, String b, int[] ind, boolean[][] edge){
        int ia = 0, ib = 0, lena = a.length(), lenb = b.length();
        while(ia < lena && ib < lenb){
            int ca = a.charAt(ia) - 'a';
            ia ++;
            int cb = b.charAt(ib) - 'a';
            ib ++;
            if(ca != cb){
                if(!edge[ca][cb]){
                    edge[ca][cb] = true;
                    ind[cb] ++;
                }
                return ;
            }
        }
    }
    /**
     * @param words: a list of words
     * @return: a string which is correct order
     */
    public String alienOrder(String[] words) {
        int[] ind = new int[26];
        boolean[][] edge = new boolean[26][26];
        boolean[] exist = new boolean[26];
        for(int i = 0; i < words.length; i ++){
            for(int j = 0; j < words[i].length(); j ++){
                exist[words[i].charAt(j) - 'a'] = true;
            }
            for(int j = i + 1; j < words.length; j ++){
                compareString(words[i], words[j], ind, edge);
            }
        }
        StringBuilder sb = new StringBuilder();
        while(true){
            int pos = -1;
            for(int i = 0; i < 26; i ++){
                if(exist[i] && ind[i] == 0){
                    pos = i;
                    break;
                }
            }
            if(pos == -1){
                break;
            }
            ind[pos] = -1;
            sb.append((char)(pos + 'a'));
            for(int i = 0; i < 26; i ++){
                if(edge[pos][i]){
                    ind[i] --;
                }
            }
        }
        // remember to check
        for(int i = 0; i < 26; i ++){
            if(exist[i] && ind[i] >= 0){
                return "";
            }
        }
        return sb.toString();
    }
}