You’re given a list of words with lowercase English letters in a different order, written in an alien language. The order of the alphabet is some permutation of lowercase letters of the English language. We have to return TRUE if the given list of words is sorted lexicographically in this alien language.

verify-alien-alphabet.js

export function verifyAlienDictionary(words, order) {
  // store letter positions in a hashmap
  // so we can get a letter position in constant time
  const foundChars = {};
  for (let i = 0; i < order.length; ++i) {
    foundChars[order[i]] = i;
  }

  // flag if the sorting is invalid
  let exit = false;

  for (let i = 0; i < words.length - 1; ++i) {
    // compare word with the next word
    const wordA = words[i];
    const wordB = words[i + 1];
    const minLen = Math.min(wordA.length, wordB.length);
    let found = false;
    // loop from 0 to min length of two words
    for (let j = 0; j < minLen; ++j) {
      // compare characters from both words
      const charA = wordA[j];
      const charB = wordB[j];
      if (charA !== charB) {
        // we found the first mismatch
        found = true;
        if (foundChars[charA] > foundChars[charB]) {
          // if charA comes after charB in the alphabet,
          // the words are not sorted correctly
          exit = true
        }
        // as soon as we find the first mismatch, we don't care about the rest of the letters in the word
        break;
      }
      // if we haven't found a mismatch, and wordB is larger than wordA
      // it means some prefix comes after a prefixed word,
      // meaning the sorting is incorrect
      if (!found && wordB.length < wordA.length) {
        exit = true;
        break;
      }
    }
  }

  if (exit) {
    // invalid sorting is found
    return false;
  }

  return true;
}

// tc: O(n+m) where n is the length of the alphabet, and m is the total length of all words
// sc: O(n) where n is the length of the alphabet