0953. Verifying an Alien Dictionary

# 953. Verifying an Alien Dictionary#

## 题目 #

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 > words, 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.

## 解题思路 #

• 这一题是简单题。给出一个字符串数组，判断把字符串数组里面字符串是否是按照 order 的排序排列的。order 是给出个一个字符串排序。这道题的解法是把 26 个字母的顺序先存在 map 中，然后依次遍历判断字符串数组里面字符串的大小。

## 代码 #

``````
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
}

`````` Sep 11, 2022 Edit this page