Question

Formatted question description: https://leetcode.ca/all/953.html

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](https://en.wikipedia.org/wiki/Lexicographical_order)).
Constraints:

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

Algorithm 1

For the normal alphabetical order, it is to compare by letter. As long as there are different letters, you can know the order of the two words. If the compared letters are the same, but one word ends early, and another word is followed by Letter, the shorter word comes first.

The overall comparison idea is still the same, that is, the alphabetical order should use its given order, so a HashMap is used to establish the mapping between the letters and their corresponding positions, so that when comparing the alphabetic order, the value can be directly taken from the HashMap. When verifying the sequence, only two pairs of verification are required. If the sequence of a pair does not match, it will directly return false.

The specific comparison method is still the same as the one mentioned earlier, comparing it letter by letter. In order to avoid crossing the boundary, only the shorter length of the two can be traversed. If the letters in the corresponding position are the same, skip directly; if the previous alphabetic order is lower, return false directly, otherwise break off (note that the reason why you cannot return true directly here is that there may be situations that do not meet the requirements of the topic. ). After that, we need to verify the situation mentioned earlier, that is, when the shorter word is a substring of a longer word, and the following word is shorter, false also needs to be returned. When the outer for loop exits normally, return true, see the code as follows:

Code 1

C++

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        unordered_map<char, int> charMap;
        for (int i = 0; i < order.size(); ++i) {
            charMap[order[i]] = i;
        }
        for (int i = 1; i < words.size(); ++i) {
            string word1 = words[i - 1], word2 = words[i];
            int n1 = word1.size(), n2 = word2.size();
            for (int j = 0; j < n1 && j < n2; ++j) {
                if (word1[j] == word2[j]) continue;
                if (charMap[word1[j]] > charMap[word2[j]]) return false;
                else break;
            }
            if (n1 > n2 && word1.substr(0, n2) == word2) return false;
        }
        return true;
    }
};

Algorithm 2

Let’s look at a more ingenious method, calling the is_sorted function inside STL. Since this function is for the normal alphabetical order, the letters in the words should be exchanged according to the order of the alien text to make it the corresponding normal Alphabetical order.

For example, if the order of the alien text is bac, then b corresponds to 0, a corresponds to 1, and c corresponds to 2. Now given two words, ba and ac, you can see at a glance that this does not conform to the normal alphabetical order , But it conforms to the order of the alien text, so it should be converted to 01 and 12. Here it is not a number, but as an ASCII code, which is the same as the letter. At this time, the comparison is the normal alphabetical order, perfect To solve it, see the code as follows:

Code 2

C++

```cppclass Solution { public: bool isAlienSorted(vector& words, string order) { vector charMap(26); for (int i = 0; i < order.size(); ++i) { charMap[order[i] - 'a'] = i; } for (string &word : words) { for (char &c : word) { c = charMap[c - 'a']; } } return is_sorted(words.begin(), words.end()); } };

```

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        Map<Character, Integer> orderMap = new HashMap<Character, Integer>();
        for (int i = 0; i < 26; i++) {
            char c = order.charAt(i);
            orderMap.put(c, i);
        }
        int length = words.length;
        for (int i = 1; i < length; i++) {
            if (compare(words[i - 1], words[i], orderMap) > 0)
                return false;
        }
        return true;
    }

    public int compare(String word1, String word2, Map<Character, Integer> orderMap) {
        if (word1.equals(word2))
            return 0;
        int length1 = word1.length(), length2 = word2.length();
        int minLength = Math.min(length1, length2);
        for (int i = 0; i < minLength; i++) {
            char c1 = word1.charAt(i), c2 = word2.charAt(i);
            int order1 = orderMap.get(c1), order2 = orderMap.get(c2);
            if (order1 != order2)
                return order1 - order2;
        }
        return length1 > length2 ? 1 : -1;
    }
}

############

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] m = new int[26];
        for (int i = 0; i < 26; ++i) {
            m[order.charAt(i) - 'a'] = i;
        }
        for (int i = 0; i < 20; ++i) {
            int prev = -1;
            boolean valid = true;
            for (String x : words) {
                int curr = i >= x.length() ? -1 : m[x.charAt(i) - 'a'];
                if (prev > curr) {
                    return false;
                }
                if (prev == curr) {
                    valid = false;
                }
                prev = curr;
            }
            if (valid) {
                break;
            }
        }
        return true;
    }
}

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        m = {c: i for i, c in enumerate(order)}
        for i in range(20):
            prev = -1
            valid = True
            for x in words:
                curr = -1 if i >= len(x) else m[x[i]]
                if prev > curr:
                    return False
                if prev == curr:
                    valid = False
                prev = curr
            if valid:
                return True
        return True

############

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

func isAlienSorted(words []string, order string) bool {
	m := make([]int, 26)
	for i, c := range order {
		m[c-'a'] = i
	}
	for i := 0; i < 20; i++ {
		prev := -1
		valid := true
		for _, x := range words {
			curr := -1
			if i < len(x) {
				curr = m[x[i]-'a']
			}
			if prev > curr {
				return false
			}
			if prev == curr {
				valid = false
			}
			prev = curr
		}
		if valid {
			break
		}
	}
	return true
}

function isAlienSorted(words: string[], order: string): boolean {
    const map = new Map();
    for (const c of order) {
        map.set(c, map.size);
    }
    const n = words.length;
    for (let i = 1; i < n; i++) {
        const s1 = words[i - 1];
        const s2 = words[i];
        const m = Math.min(s1.length, s2.length);
        let isEqual = false;
        for (let j = 0; j < m; j++) {
            if (map.get(s1[j]) > map.get(s2[j])) {
                return false;
            }
            if (map.get(s1[j]) < map.get(s2[j])) {
                isEqual = true;
                break;
            }
        }
        if (!isEqual && s1.length > s2.length) {
            return false;
        }
    }
    return true;
}

use std::collections::HashMap;
impl Solution {
    pub fn is_alien_sorted(words: Vec<String>, order: String) -> bool {
        let n = words.len();
        let mut map = HashMap::new();
        order.as_bytes().iter().enumerate().for_each(|(i, &v)| {
            map.insert(v, i);
        });
        for i in 1..n {
            let s1 = words[i - 1].as_bytes();
            let s2 = words[i].as_bytes();
            let mut is_equal = true;
            for i in 0..s1.len().min(s2.len()) {
                if map.get(&s1[i]) > map.get(&s2[i]) {
                    return false;
                }
                if map.get(&s1[i]) < map.get(&s2[i]) {
                    is_equal = false;
                    break;
                }
            }
            if is_equal && s1.len() > s2.len() {
                return false;
            }
        }
        true
    }
}

953 - Verifying an Alien Dictionary

Question

Algorithm 1

Code 1

Algorithm 2

Code 2

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm 1

Code 1

Algorithm 2

Code 2

All Problems

All Solutions