953. Verifying an Alien Dictionary #

Problem #

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The orderof 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.

Example 3:

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

Note:

1. 1 <= words.length <= 100
2. 1 <= words[i].length <= 20
3. order.length == 26
4. All characters in words[i] and order are english lowercase letters.

Problem Summary #

A certain alien language also uses English lowercase letters, but the order may be different. The alphabet order (order) is a permutation of lowercase letters. Given a set of words words written in the alien language, as well as the alphabet order order, return true only if the given words are sorted lexicographically in this alien language; otherwise, return false.

Solution Approach #

• This is an easy problem. Given a string array, determine whether the strings in the array are arranged according to the sorting order of order. order is a given string ordering. The solution to this problem is to first store the order of the 26 letters in a map, and then iterate through the string array to compare the strings in order.

Code #

package leetcode

func isAlienSorted(words []string, order string) bool {
	if len(words) < 2 {
		return true
	}
	hash := make(map[byte]int)
	for i := 0; i < len(order); i++ {
		hash[order[i]] = i
	}
	for i := 0; i < len(words)-1; i++ {
		pointer, word, wordplus := 0, words[i], words[i+1]
		for pointer < len(word) && pointer < len(wordplus) {
			if hash[word[pointer]] > hash[wordplus[pointer]] {
				return false
			}
			if hash[word[pointer]] < hash[wordplus[pointer]] {
				break
			} else {
				pointer = pointer + 1
			}
		}
		if pointer < len(word) && pointer >= len(wordplus) {
			return false
		}
	}
	return true
}