# 953. Verifying an Alien Dictionary 验证外星语词典

@TOC

## # 题目描述

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

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.

## # 解题方法

``````class Solution(object):
def isAlienSorted(self, words, order):
"""
:type words: List[str]
:type order: str
:rtype: bool
"""
N = len(words)
d = {c : i for i, c in enumerate(order)}
for i in range(N - 1):
pre, after = words[i], words[i + 1]
if pre == after: continue
_len = min(len(pre), len(after))
for j in range(_len):
if d[pre[j]] < d[after[j]]:
break
elif d[pre[j]] > d[after[j]]:
return False
if len(pre) > len(after) and pre[:_len] == after:
return False
return True
``````

## # 日期

2018 年 12 月 9 日 —— 周赛懵逼了