#953 Verifying an Alien Dictionary

1class Solution {2    /** Rewrite every word into normal letters ('a' = alien first letter), then check sortedness. */3    public boolean isAlienSorted(String[] words, String order) {4        char[] map = new char[26];5        for (int i = 0; i < 26; i++) map[order.charAt(i) - 'a'] = (char) ('a' + i);6        String[] translated = new String[words.length];7        for (int w = 0; w < words.length; w++) {8            StringBuilder sb = new StringBuilder();9            for (char ch : words[w].toCharArray()) sb.append(map[ch - 'a']);10            translated[w] = sb.toString();11        }12        String[] sorted = translated.clone();13        Arrays.sort(sorted);14        return Arrays.equals(sorted, translated);15    }16}

1class Solution {2    public boolean isAlienSorted(String[] words, String order) {3        int[] rank = new int[26];4        for (int i = 0; i < 26; i++) rank[order.charAt(i) - 'a'] = i;5        for (int w = 0; w + 1 < words.length; w++) {6            if (!inOrder(words[w], words[w + 1], rank)) return false;7        }8        return true; // sortedness only needs ADJACENT pairs (it is transitive)9    }10 11    private boolean inOrder(String a, String b, int[] rank) {12        int len = Math.min(a.length(), b.length());13        for (int i = 0; i < len; i++) {14            char x = a.charAt(i), y = b.charAt(i);15            if (x != y) return rank[x - 'a'] < rank[y - 'a']; // first difference decides16        }17        return a.length() <= b.length(); // "apple" before "app" is wrong18    }19}