Hash table: whether alien languages are sorted

subject

Hashtable ： Whether alien languages are sorted
https://leetcode-cn.com/problems/lwyVBB/

Their thinking

1. Two conditions for judging word order
Suppose there are two words ,word1 and word2.
word1 and word2 When the letters are not equal for the first time ,word1[i] < word2[i], So these two words are ordered , Otherwise it is disordered .

If two words have equal letters , The length of the preceding word is greater than that of the following word , So these two words are not ordered .

2. Save the index reference hash table indicating the size of letters .
We use the keys of the hash table to save the letters of the words , The value of the hash table holds the sequence number of the letters of the word .
The smaller the serial number , Indicates that the smaller the letter .
The length of the hash table is 26, because order The sequence string represents at most 26 Letters .

3. Compare letter sizes
From the hash table according to the key （ Letter -‘a’）, You can get the size of letters directly .

The specific code is as follows ：

Code

class Solution {
    
    public boolean isAlienSorted(String[] words, String order) {
    
        int[] orderArray = new int[order.length()];
        for(int i = 0; i < order.length(); i++) {
    
            orderArray[order.charAt(i) - 'a'] = i;
        }
        for(int i = 0; i < words.length - 1; i++) {
    
            String w1 = words[i];
            String w2 = words[i+1];
            boolean isSorted = isSorted(w1, w2, orderArray);
            if(!isSorted){
    
                return false;
            }
        }
        return true;
    }

    private boolean isSorted(String word1, String word2, int[] order) {
    
        int i = 0;
        for(; i < word1.length() && i < word2.length(); ++i) {
    
            char char1 = word1.charAt(i);
            char char2 = word2.charAt(i);

            if(order[char1 - 'a'] < order[char2 - 'a']) {
    
                return true;
            }
              if(order[char1 - 'a'] > order[char2 - 'a']) {
    
                return false;
            }
        }

        return i == word1.length();
    }

}

summary

This topic examines the application of hash tables . Determine letter size , You can use hash tables / The array stores the letters and their sizes .