953. Verifying an Alien Dictionary

LeetCode 953. Verifying an Alien Dictionary

Description

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.

Example 2:

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

Constraints:

• 1 <= words.length <= 100

• 1 <= words[i].length <= 20

• order.length == 26

• All characters in words[i] and order are English lowercase letters.

Tags

Hash Table

Solution

Before checking, we build a dictionary to map each character from order to its index. We compare each pair of adjacent words. Iterate over the former word.

• If the pointer on the word[i] is beyond the length of word[i+1], return false. Because the latter mush longer than or equal to the former word if they share the same prefix;

• If words[i][j] != words[i+1][j], retrieve the indices of both and they must obey the alien dictionary order. After evaluating, break here because the remain part will not be considered.

Complexity

• Time complexity: $O(mn)$

• Space complexity: $O(1)$

Code

func isAlienSorted(words []string, order string) bool {
	dict := map[byte]int{}
	for i, c := range order {
		dict[byte(c)] = i
	}
	for i := 0; i < len(words)-1; i++ {
		for j := 0; j < len(words[i]); j++ {
			// if both words share the same prefix, the latter must ≥ the former
			if j >= len(words[i+1]) {
				return false
			}
			// the corresponding position must in alien dict order
			if words[i][j] != words[i+1][j] {
				if dict[words[i][j]] > dict[words[i+1][j]] {
					return false
				}
				break // the remain part will not be considered
			}
		}
	}
	return true
}

Reference

1. 验证外星语词典