# 953. Verifying an Alien Dictionary

## LeetCode [953. Verifying an Alien Dictionary](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### 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

```go
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. [验证外星语词典](https://leetcode-cn.com/problems/verifying-an-alien-dictionary/solution/yan-zheng-wai-xing-yu-ci-dian-by-leetcode/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/953.-verifying-an-alien-dictionary.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.