953. Verifying an Alien Dictionary
Easy
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 lexicographically 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 ().
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 20order.length == 26- All characters in
words[i]andorderare English lowercase letters.
func isAlienSorted(words []string, order string) bool {
m := make(map[byte]int)
for i:=0; i<len(order); i++ { // 將字母與 order 做對應
m[order[i]] = i
}
for i:=1; i<len(words); i++ {
// 如果 words[i] 沒有大於前一個，則回傳 false
if !compare(words[i], words[i - 1], m) { return false }
}
return true
}
func compare(w1, w2 string, m map[byte]int) bool {
for i := 0; i < len(w1) && i < len(w2); i++ {
if w1[i] != w2[i] {
if m[w1[i]] > m[w2[i]] {
return true
} else {
return false
}
}
}
return len(w1) >= len(w2) // 字母都相同時，長度較短的應該排在前面
}