Verifying an Alien Dictionary

NeetCode: Verifying an Alien Dictionary · LeetCode: 953. Verifying an Alien Dictionary · Difficulty: Easy

Given an array of words written in an alien language and the order of its 26 lowercase letters, return true if the words are sorted lexicographically in that language.

Example

Text

Input:  words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"    Output: true
Input:  words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"  Output: false
Input:  words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"          Output: false

Two words compare by their first differing letter; if one is a prefix of the other, the shorter word comes first.

Brute force: compare every pair of words

Build a rank array mapping each letter to its position in order. A sorted list means every earlier word is <= every later word, so check all pairs i < j. This is quadratic in the number of words.

Java

class Solution {
    // True when word a is <= word b in the alien order.
    private boolean le(String a, String b, int[] rank) {
        int len = Math.min(a.length(), b.length());
        for (int i = 0; i < len; i++) {
            int x = rank[a.charAt(i) - 'a'];
            int y = rank[b.charAt(i) - 'a'];
            if (x != y) {
                return x < y;
            }
        }
        return a.length() <= b.length();
    }

    public boolean isAlienSorted(String[] words, String order) {
        int[] rank = new int[26];
        for (int i = 0; i < order.length(); i++) {
            rank[order.charAt(i) - 'a'] = i;
        }
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (!le(words[i], words[j], rank)) {
                    return false;
                }
            }
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        String abc = "abcdefghijklmnopqrstuvwxyz";
        System.out.println(s.isAlienSorted(new String[]{"hello", "leetcode"}, "hlabcdefgijkmnopqrstuvwxyz"));
        System.out.println(s.isAlienSorted(new String[]{"word", "world", "row"}, "worldabcefghijkmnpqstuvxyz"));
        System.out.println(s.isAlienSorted(new String[]{"apple", "app"}, abc));
        System.out.println(s.isAlienSorted(new String[]{}, abc));
    }
}

Output

true
false
false
true

Time: O(k^2 * L) for k words of length up to L. Space: O(1).

Optimal: compare adjacent words only

The order relation is transitive: if w0 <= w1 and w1 <= w2 then w0 <= w2. So it is enough to check each neighbouring pair. Each character is examined at most twice, so the work is linear in the input size.

Java

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] rank = new int[26];
        for (int i = 0; i < order.length(); i++) {
            rank[order.charAt(i) - 'a'] = i;
        }
        for (int w = 0; w + 1 < words.length; w++) {
            String a = words[w];
            String b = words[w + 1];
            boolean decided = false;
            int len = Math.min(a.length(), b.length());
            for (int i = 0; i < len; i++) {
                int x = rank[a.charAt(i) - 'a'];
                int y = rank[b.charAt(i) - 'a'];
                if (x != y) {
                    if (x > y) {
                        return false;
                    }
                    decided = true;
                    break;
                }
            }
            if (!decided && a.length() > b.length()) {
                return false;
            }
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        String abc = "abcdefghijklmnopqrstuvwxyz";
        System.out.println(s.isAlienSorted(new String[]{"hello", "leetcode"}, "hlabcdefgijkmnopqrstuvwxyz"));
        System.out.println(s.isAlienSorted(new String[]{"word", "world", "row"}, "worldabcefghijkmnpqstuvxyz"));
        System.out.println(s.isAlienSorted(new String[]{"apple", "app"}, abc));
        System.out.println(s.isAlienSorted(new String[]{}, abc));
    }
}

Output

true
false
false
true

Time: O(total characters). Space: O(1) (the 26-entry array).