LeetCode 953 - Verifying an Alien Dictionary

https://leetcode.com/problems/verifying-an-alien-dictionary/

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

Example 1:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

https://leetcode.com/articles/verifying-an-alien-dictionary/
Time Complexity: $O(\mathcal{C})$, where $\mathcal{C}$ is the total content of words.

The words are sorted lexicographically if and only if adjacent words are. This is because order is transitive: a <= b and b <= c implies a <= c.

Algorithm

Let's check whether all adjacent words a and b have a <= b.

To check whether a <= b for two adjacent words a and b, we can find their first difference. For example, "applying" and "apples" have a first difference of y vs e. After, we compare these characters to the index in order.

Care must be taken to deal with the blank character effectively. If for example, we are comparing "app" to "apply", this is a first difference of (null) vs "l".

  public boolean isAlienSorted(String[] words, String order) {

    int[] index = new int[26];

    for (int i = 0; i < order.length(); ++i)

      index[order.charAt(i) - 'a'] = i;

    search: for (int i = 0; i < words.length - 1; ++i) {

      String word1 = words[i];

      String word2 = words[i + 1];

      // Find the first difference word1[k] != word2[k].

      for (int k = 0; k < Math.min(word1.length(), word2.length()); ++k) {

        if (word1.charAt(k) != word2.charAt(k)) {

          // If they compare badly, it's not sorted.

          if (index[word1.charAt(k) - 'a'] > index[word2.charAt(k) - 'a'])

            return false;

          continue search;

        }

      }

      // If we didn't find a first difference, the

      // words are like ("app", "apple").

      if (word1.length() > word2.length())

        return false;

    }

    return true;

  }

https://leetcode.com/problems/verifying-an-alien-dictionary/discuss/203185/JavaC%2B%2BPython-Mapping-to-Normal-Order

Build a transform mapping from order,
Find all alien words with letters in normal order.

For example, if we have order = "xyz..."
We can map the word "xyz" to "abc" or "123"

Then we check if all words are in sorted order.

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

    int compare(String s1, String s2) {
        int n = s1.length(), m = s2.length(), cmp = 0;
        for (int i = 0, j = 0; i < n && j < m && cmp == 0; i++, j++) {
            cmp = mapping[s1.charAt(i) - 'a'] - mapping[s2.charAt(j) - 'a'];
        }
        return cmp == 0 ? n - m : cmp;
    }