Verifying an Alien Dictionary

We are given a list of words and a specific order of characters in an alien language. We need to determine if the words are sorted lexicographically according to this alien language.

Approach

  1. Create a Mapping: Create a mapping of each character to its index according to the given order. This will help us compare the characters in the words.

  2. Compare Adjacent Words: Iterate through the list of words and compare each word with the next one to check if they are sorted.

  3. Compare Characters: For each pair of adjacent words, compare their characters one by one. If we find a character that is larger in the first word than in the second, return False, as this means the words are not sorted. If the characters are equal, continue to the next character. If the first word is a prefix of the second, continue to the next pair of words.

  4. Handle Edge Case: If one word is a prefix of the other (e.g., “app” and “apple”), the shorter word should come first. If not, return False.

  5. Return True: If all adjacent words are sorted, return True.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        alien_order = {char: index for index, char in enumerate(order)}

        for i in range(len(words) - 1):
            word1 = words[i]
            word2 = words[i + 1]

            # If the first word is longer and a prefix of the second, it is unsorted
            if len(word1) > len(word2) and word1[:len(word2)] == word2:
                return False

            for j in range(min(len(word1), len(word2))):
                char1 = word1[j]
                char2 = word2[j]

                # If characters are not sorted, return False
                if alien_order[char1] > alien_order[char2]:
                    return False
                # If characters are sorted, no need to check the remaining characters
                elif alien_order[char1] < alien_order[char2]:
                    break

        return True

Example

  • Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
  • Output: true
  • Explanation: Since ‘h’ comes before ’l’ in this language, the sequence is sorted.

Insights

  • Time Complexity: The time complexity of this solution is (O(n \cdot m)), where (n) is the number of words, and (m) is the maximum length of a word.
  • Space Complexity: The space complexity is (O(1)), as we are only using a constant amount of extra space (not counting the input itself).
  • Utilizing Custom Order: The solution efficiently utilizes the given custom order by mapping the characters to their indices, making it easy to compare them.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# @param {String[]} words
# @param {String} order
# @return {Boolean}
def is_alien_sorted(words, order)
  hash = {}
  order.chars.each_with_index do |c, i|
     hash[c] = i 
  end
  
  for i in (1...words.size)
     first = words[i-1]
     second = words[i]

# first character in the first word must have higher value than the first character in the second word.   
      j = 0
      min = [first.size, second.size].min

      while j < min 
        if first[j] != second[j] 
          if hash[first[j]] < hash[second[j]] 
              break
          else
            return false
          end
        else
          j += 1
        end
      end
      if j == min && j < first.size
          return false
      end
  end
#   hello == hello 
  return true
end