LeetCode 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 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 (More info).

Constraints:

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

---

这道题给了一个重新定义的字母顺序，问你一个数组里的string是否是按给定的顺序字典序排序的。刚开始有点懵，其实就直接把新定义的顺序map到原始的顺序里，然后写一个字典序排序的helper function，对整个数组比较一遍就行了。这里就注意一下字典序排序的规则：

1. 如果两个字符不一样，那就看谁前谁后

2. 如果比较到最后一个字符了都还一样，那就短的在前长的在后

因为这里的helper只需要判断是否sorted，所以直接return true/false，最后要记得<=（刚开始没注意只写了<……）

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        Map<Character, Character> map = new HashMap<>();
        for (int i = 0; i < order.length(); i++) {
            map.put(order.charAt(i), (char)('a' + i));
        }
 
        for (int i = 1; i < words.length; i++) {
            if (!sorted(words[i - 1], words[i], map)) {
                return false;
            }
        }
        return true;
    }
 
    boolean sorted(String a, String b, Map<Character, Character> map) {
        int lenA = a.length();
        int lenB = b.length();
 
        for (int i = 0; i < lenA && i < lenB; i++) {
            if (a.charAt(i) != b.charAt(i)) {
                return map.get(a.charAt(i)) < map.get(b.charAt(i));
            }
        }
        return lenA <= lenB;
    }
}