[Facebook] 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 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).

 

Constraints:

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

 

 

외계인 언어에서는 놀랍게도 영어 소문자도 사용하지만 순서가 다를 수 있습니다.
알파벳의 순서는 소문자의 일부 순열입니다.
외국어로 쓰여진 일련의 단어와 알파벳 순서가 주어지면 주어진 단어가이 외국어로 사전 순으로 정렬 된 경우에만 true를 반환합니다.

예 1 : 입력 : words = [ "hello", "leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
출력 : true 설명 :이 언어에서 'h'가 'l'앞에 오므로 시퀀스가 ​​정렬됩니다.

예 2 : 입력 : words = [ "word", "world", "row"], order = "worldabcefghijkmnpqstuvxyz"
출력 : false 설명 :이 언어에서 'd'가 'l'뒤에 오면 words [0]> words [1 ]이므로 시퀀스가 ​​정렬되지 않습니다.

예 3 : 입력 : words = [ "apple", "app"], order = "abcdefghijklmnopqrstuvwxyz"
출력 : false 설명 : 처음 세 문자 "app"이 일치하고 두 번째 문자열이 더 짧습니다 (크기).

사전 규칙 "apple ">"app ", 'l'> '∅', 여기서 '∅'는 다른 문자보다 적은 공백 문자로 정의됩니다 (추가 정보). 제약 : 1 <= 단어 길이 <= 100 1 <= 단어 [i] .length <= 20 order.length == 26 단어 [i]와 순서의 모든 문자는 영문 소문자입니다.

---

Solution

---

Approach 1: Check Adjacent Words

Intuition

The words are sorted lexicographically if and only if adjacent words are. This is because order is transitive: a <= b and b <= c implies a <= c.

Algorithm

Let's check whether all adjacent words a and b have a <= b.

To check whether a <= b for two adjacent words a and b, we can find their first difference. For example, "applying" and "apples" have a first difference of y vs e. After, we compare these characters to the index in order.

Care must be taken to deal with the blank character effectively. If for example, we are comparing "app" to "apply", this is a first difference of (null) vs "l".

 

접근 방식 1 : 인접 단어 확인

직관

단어는 인접한 단어가있는 경우에만 사전 순으로 정렬됩니다. 이는 순서가 전이 적이기 때문입니다. a <= b 및 b <= c는 a <= c를 의미합니다.

연산

인접한 모든 단어 a와 b가 a <= b인지 확인해 봅시다.

인접한 두 단어 a와 b에 대해 a <= b인지 확인하기 위해 첫 번째 차이점을 찾을 수 있습니다. 예를 들어, "적용"과 "사과"의 첫 번째 차이는 y와 e입니다. 그런 다음 이러한 문자를 순서대로 색인과 비교합니다.

공백 문자를 효과적으로 처리하려면주의해야합니다. 예를 들어 "app"과 "apply"를 비교하는 경우 이것은 (null) 대 "l"의 첫 번째 차이입니다.

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] index = new int[26];
        for (int i = 0; i < order.length(); ++i)
            index[order.charAt(i) - 'a'] = i;

        search: for (int i = 0; i < words.length - 1; ++i) {
            String word1 = words[i];
            String word2 = words[i+1];

            // Find the first difference word1[k] != word2[k].
            for (int k = 0; k < Math.min(word1.length(), word2.length()); ++k) {
                if (word1.charAt(k) != word2.charAt(k)) {
                    // If they compare badly, it's not sorted.
                    if (index[word1.charAt(k) - 'a'] > index[word2.charAt(k) - 'a'])
                        return false;
                    continue search;
                }
            }

            // If we didn't find a first difference, the
            // words are like ("app", "apple").
            if (word1.length() > word2.length())
                return false;
        }

        return true;
    }
}

 

Complexity Analysis

• Time Complexity: O(\mathcal{C})O(C), where \mathcal{C}C is the total content of words.

• Space Complexity: O(1)O(1).