subject

This is [034, modified phrase] on LeetCode. The difficulty is [simple]

Some alien languages also use English lowercase letters, but the order may be different. The order of the alphabet is the arrangement of lowercase letters.

Given a set of words written in an alien language and the order of its alphabet, it returns true only when the given words are arranged in dictionary order in this alien language; Otherwise, false is returned.

Example 1

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
 Explanation: in the alphabet of the language,'h' be located 'l' Before, so the word sequence is arranged in dictionary order.

Example 2:

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
 Explanation: in the alphabet of the language,'d' be located 'l' After that, then words[0] > words[1]，Therefore, the word sequence is not arranged in dictionary order.

Example 3:

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
 Explanation: current three characters "app" When matching, the second string is relatively short, and then according to the lexicography rules "apple" > "app"，because 'l' > '∅'，among '∅' Is a white space character defined as smaller than any other character (more information)

Tips:

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

Problem solution

Train of thought analysis

According to the meaning of the title, the order of the alphabet of alien languages is different from that of the conventional English character table. Therefore, we need a hash table to record the order of the alphabet of alien languages. The keys of the hash table store the characters of the alphabet, and the values of the hash table store the order of the alphabet

Since there are only 26 English letters, we can create an int array with a capacity of 26 to simulate the hash table. The subscript of the array corresponds to the key (letter) of the hash table, and the value of the array corresponds to the value (letter order) of the hash table

step

Create an int array analog hash table with a capacity of 26, with subscripts corresponding to letters and values corresponding to the order of letters

Traverse the alphabet (string) of alien language to obtain each letter in the alphabet. The index of the current letter in the array can be obtained by subtracting a from the current letter in the traversal process. The value of the index of the current array is assigned to the index of the current traversal, that is, the order of the letters in the alphabet

Traverse the word group, and compare the size of the current word and the next word of the current word. If the current word is less than the next word of the current word, it meets the alien language alphabet. Comparing the size of words is actually comparing the character size of words. It is discussed in three cases below

1. The condition is met when the first character of the first word is less than the first character of the second word

2. When the first character of the first word is greater than the first character of the second word, the condition is not met

3. When the first character of the first word is equal to the first character of the second word, continue to compare the next character of the two words. When the short words are equal after comparison, there will be two cases

   • If the characters in front of the first word are equal to the second word, the first word is greater than the second word and does not meet the conditions
   • If the first word is equal to the characters in front of the second word, the first word is less than the second word and meets the conditions

It should be noted that the end condition for traversing words is the length of the word group minus 1, because each traversal compares two words.

code implementation

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        // Create an int array analog hash table with a capacity of 26, with subscripts corresponding to letters and values corresponding to the order of letters
        int [] orderArray = new int[order.length()];
        /* Traversing the alphabet (string) of an alien language to obtain each letter in the alphabet,
        The index of the current letter in the array can be obtained by subtracting a from the current letter in the traversal process,
        The value of the index of the current array is assigned to the index of the current traversal, that is, the order of letters in the alphabet*/
        for (int i = 0; i < order.length(); i++) {
            orderArray[order.charAt(i) - 'a'] = i;
        }
        // Traverse the word group, and compare the size of the current word with the next word of the current word
        for (int i = 0; i < words.length -1; i++) {
            if (!isSorted(words[i], words[i + 1], orderArray)) {
                return false;
            }
        }
        return true;
    }

    private boolean isSorted(String word1, String word2, int[] orderArray) {
        int i = 0;
        // Traverse the characters of the current word and the next word of the current word to compare the size
        for (; i < word1.length() && i < word2.length(); i++) {
            char char1 = word1.charAt(i);
            char char2 = word2.charAt(i);
            // If the character of the current word is less than the character of the next word of the current word, the sequence table is satisfied
            if (orderArray[char1 - 'a'] < orderArray[char2 - 'a']) {
                return true;
            }
            // If the sequence table is not satisfied, if this condition is not executed, the two characters are equal and continue to interpret the next character
            if (orderArray[char1 - 'a'] > orderArray[char2 - 'a']) {
                return false;
            }
        }
        /* When the loop is terminated by the loop condition, that is, the two words are different in length, but the characters in the front of the short word and the long word are equal
            There are two situations when the short word is terminated after traversal
        * If the characters in front of the first word are equal to the second word, the first word is greater than the second word and does not meet the conditions
        * If the first word is equal to the characters in front of the second word, the first word is less than the second word and meets the conditions
        * Therefore, you only need to judge whether the first word is equal to i. if it is equal to i, the first word is shorter than the second word
          And less than the second word*/
        return i == word1.length();
    }
}

Complexity analysis

Suppose n words are input, and the average length of each word is m

Time complexity

Words need to be traversed, and the characters of each word need to be traversed in the process of traversing words, so the time complexity is O(nm)

Spatial complexity

An array with fixed capacity is declared, so the space complexity is O(1)