My kn^2 Java solution. K is the average number of distinct characters per word and n is the number of words


  • 0
    J

    Here is my solution with comment, easy to understand.
    Here are explains:
    'w'>'f'
    We call this as a rule and represented as char[] {w, f};
    Which means 'w' should go ahead of 'f'.
    Now if we really think about when we sort list of strings how we gonna to compare them.
    Say, "abc", "acd". We will compare them from head to tail when we first come to something different. Then the order is determined by that char, which is b>c.
    Now we know how we can get a list of rules from the words.
    Next question is, how we gonna to chain those rules together.
    Suppose we have rules as:
    a>b
    b>c
    c>d
    We check all left side of rules. We find d is missing. Then we know, d is the last one. Then we remove rules which has d on the right side because these rules wont help next. Now rules come to:
    a>b
    b>c
    we do same thing until rule set is empty. We get dcba and we just reverse it.
    Below is the code:

    class Solution {
        public String alienOrder(String[] words) {
            if(words==null || words.length==0) return "";
            Set<char[]> rules = new HashSet<>();
            Set<Character> chars = new HashSet<>();
            for(String word:words) {
                for(int i=0;i<word.length();i++) chars.add(word.charAt(i));
            }
            for(int i=1;i<words.length;i++) {
                int p = 0;
                while(p<words[i-1].length() && p<words[i].length()) {
                    if(words[i-1].charAt(p)!=words[i].charAt(p)) {
                        char[] newRule = new char[2];
                        newRule[0] = words[i-1].charAt(p);
                        newRule[1] = words[i].charAt(p);
                        rules.add(newRule);
                        break;
                    } else p++;
                }
            }
            Map<Character, List<char[]>> rightCharToRule = new HashMap<>();
            for(char[] rule: rules) {
                List<char[]> cToRule = rightCharToRule.get(rule[1]);
                if(cToRule==null) cToRule = new LinkedList<>();
                cToRule.add(rule);
                rightCharToRule.put(rule[1],cToRule);
            }
            StringBuilder sb = new StringBuilder();
            boolean modified = true;
            while(!rules.isEmpty() && modified) {
                Set<Character> leftSideChars = new HashSet<>();
                for(char[] rule:rules) {
                    leftSideChars.add(rule[0]);
                }
                List<char[]> rmRule = new LinkedList<>();
                Iterator<Character> itor = chars.iterator();
                while(itor.hasNext()) {
                    Character c = itor.next();
                    if(leftSideChars.contains(c)) continue;
                    else {
                        sb.append(c);
                        if(rightCharToRule.get(c)!=null) rmRule.addAll(rightCharToRule.get(c));
                        itor.remove();
                    }
                }
                modified = false;
                for(char[] rule:rmRule) {
                    rules.remove(rule);
                    modified = true;
                }
            }
            for(Character c: chars) sb.append(c);
            if(!rules.isEmpty()) return "";
            return sb.reverse().toString();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.