Leetcode.com problem 953: "Verifying an Alien Dictionary"

James S. Plank

• Problem Statement.

• Category: Easy
• Success Rate (as of February, 2023): 54.3%
• Skeleton.cpp: A skeleton file with a main.
• Solution.cpp: A solution.

In Case Leetcode's Servers are Down

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order);
};

• words is a vector of words, size between 1 and 100 elements.
• Each element of words is composed of lower-case letters, size between 1 and 20 characters.
• order is a string whose length is 26. It contains all of the lowercase letters, and defines an alternate ordering of the letters.
• For example, if order is "worldabcefghijkmnpqstuvxyz", then 'w' is the first character, 'o' is the second, and so on.
• You are to compare each consecutive word in words, and if words[i] is lexicographically less than words[i-1] given the letter ranking in order, then return false.
• Otherwise return true.

Examples

• Example 1:
  words = { "hello", "leetcode" }.
  order = "hlabcdefgijkmnopqrstuvwxyz".
  Answer = true.

• Example 2:
  words = { "word", "world", "row" }.
  order = "worldabcefghijkmnpqstuvxyz".
  Answer = false.

• Example 3:
  words = { "apple", "app" }.
  order = "abcdefghijklmnopqrstuvwxyz".
  Answer = false.

• Example 4:
  words = { "zyx", "zyw" }.
  order = "zyxwvutsrqponmlkjihgfedcba".
  Answer = true.

  What the order here means is that the characters are ordered backward from their normal order -- 'z' is the smallest, 'y' is the next, and so on. So it should be clear that "zyx" is "smaller" than "zyw".

Hints

Let's take that last example as an example. Since 'z' is the first character in order, we can convert any 'z' in words to an 'a', which is the first character in the normal order of the alphabet. Similarly, we'll convert 'y' to 'b', 'x' to 'c' and 'w' to 'd'. When we do that, words becomes "abc" and "abd", and we can use string comparison to verify that they are in the correct order.

To perform this conversion, I use a string called trans, where trans[i] is equal to the character to which I convert character 'a'+i. Let's use example 2 above. Here's what I want the translation to be:

In other words, we'll convert 'w' to 'a', 'o' to 'b', etc. Accordingly, here is trans -- I put an alphabet on top so you can see what letters each character corresponds to:

         abcdefghijklmnopqrstuvwxyz
trans = "fhgeijklmnodpqbrsctuvwaxyz"

To convert a word using trans, we replace each letter with the letter it corresponds to in trans. For example, "word" is converted to "abce", and "word" is "abcde". Now, we can see that "word" is greater than "world", because "abce" is greater than "abcde."

Solution

bool Solution::isAlienSorted(vector<string>& words, string order)
{
  string trans;
  int i, j;

  /* Create trans.  Trans[i-'a'] contains the character that character i
     should translate to (such as 'w' to 'a' in Example 4). */

  trans.resize(26, ' ');
  for (i = 0; i < order.size(); i++) trans[order[i]-'a'] = 'a' + i;

  /* Go through the words vector, and convert each word. */

  for (i = 0; i < words.size(); i++) {
    for (j = 0; j < words[i].size(); j++) {
      words[i][j] = trans[words[i][j]-'a'];
    }
    /* Compare each word to the one that precedes it, and if it is
       smaller, then the words are not in order -- return false. */

    if (i > 0 && words[i] < words[i-1]) return false;
  }

  /* If you get here without any words out of order, return true. */

  return true;
}

Verify that it works on the examples:

UNIX> echo hello leetcode hlabcdefgijkmnopqrstuvwxyz | ./a.out
True
UNIX> echo word world row worldabcefghijkmnpqstuvxyz | ./a.out
False
UNIX> echo apple app abcdefghijklmnopqrstuvwxyz | ./a.out
False
UNIX> echo zyx zyw zyxwvutsrqponmlkjihgfedcba | ./a.out
True
UNIX>