FOB
Blog

Verify Alien Dictionary – LeetCode Solutions

So this is the much simpler cousin of the “Create an Alien Dictionary” problem which potentially involves creating a graph data structure and doing a topological sort of the nodes.

In this problem you start with a scrambled alphabet, and then determine if a list of words are sorted “alphabetically”.

The only challenge here is figuring out the subproblem, which is: determine if two words are in order.

To do that, we’re checking to make sure that the first letter in that word comes before the first letter in the second word.

The complexity comes from asking the question: what if the first letter of word A is the same as the first letter of word B?

And the answer is, we go to the second letter if we have to, and the third, all the way to the end of the word.

The last caveat is, if all the letters of word A match all the letters of word B, and B is either the same length or longer than word A, then we’re good.

/**
 * @param {string[]} words
 * @param {string} order
 * @return {boolean}
 */
var isAlienSorted = function(words, order) {
    order = order.split("")
    const correctOrder = (a, b) =>{
      let n = a.length
      for(let i = 0; i < n; i++){
        const ai = order.indexOf(a[i])
        const bi = order.indexOf(b[i])
        if(ai == bi)
          continue
        return ai < bi
      }
      return true
    }
    
    for(let i = 0; i < words.length - 1; i++){
      if(!correctOrder(words[i], words[i+1]))
        return false
    }
    return true
};

So you’ll see I wrote this “correctOrder” function to compare any two words to see if they fit the defined order of our alphabet.

Once that part is debugged, the last part, iterating through the whole word list, is very trivial.

Lots of problems fit this “fit all the constraints” paradigm where we’re aborting as soon as a constraint is failed, otherwise the loops run to completion and the last thing we do is return “true” to indicate that nothing went wrong.

Let's get started

Just let us know the basics and we'll send you a Slack invite to discuss with the whole team.

What are we going to be talking about?

%d bloggers like this: