Detailed explanation of the example of the 953 verification of the alien dictionary

Question description

953. Verify the alien dictionary

Some alien language also uses lowercase letters in English, but may be in sequenceorderdifferent. The order of the alphabet (order) is a arrangement of some lowercase letters.

Given a set of words written in alien languagewords, and the order of its alphabetorder, only when the given word is arranged in dictionary order in this alien language, returntrue; Otherwise, returnfalse。

Example 1:

enter：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output：true
explain：In the alphabet of the language，'h' lie in 'l' Before，So the word sequence is arranged in dictionary order。

Example 2:

enter：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output：false
explain：In the alphabet of the language，'d' lie in 'l' after，So words[0] &amp;gt; words[1]，Therefore, word sequences are not arranged in dictionary order。

Example 3:

enter：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output：false
explain：The current three characters "app" When matching，The second string is relatively short，Then according to the lexicon rules "apple" &amp;gt; "app"，because 'l' &amp;gt; '∅'，in '∅' is a blank character，Defined as smaller than any other character（More information）。

hint:

1 <= <= 100

1 <= words[i].length <= 20

== 26

All characters in words[i] and order are in lowercase English letters.

Idea Analysis

The hash table stores letters and corresponding indexes. You must use it when judging the sequence of strings.
Then compare the two strings and choose a shorter length to compare
The index in the dictionary corresponding to a[i] is indexA;
The index in the dictionary corresponding to b[i] is indexB;
If indexA < indexB, return true directly;
If indexA > indexB, return false directly;
If the first minLen characters are equal, finally determine the length of the string

AC Code

class Solution {
public:
    bool compare(string& a, string& b, unordered_map<char, int>& mp) {
        int sizeA = ();
        int sizeB = ();
        int minLen = sizeA > sizeB ? sizeB : sizeA;
        int same = 0;
        for (int i = 0; i < minLen; i++) {
            if (mp[a[i]] < mp[b[i]]) {
                return true;
            } else if(mp[a[i]] > mp[b[i]]) { 
                return false;
            }else if (mp[a[i]] == mp[b[i]]) {
                same++;
            }
        }
        if (same == minLen) {
            return () < ();
        }
        return false;
    }
    bool isAlienSorted(vector<string>& words, string order) {
        unordered_map<char, int> mp;
        for (int i = 0; i < 26; i++) {
            mp[order[i]] = i;
        }
        int size = ();
        if (size == 1) {
            return true;
        }
        for (int i = 0; i < (size - 1); i++) {
            if (compare(words[i], words[i+1], mp) == false) {
                return false;
            }
        }
        return true;
    }
};

The above is the detailed explanation of the example of the Go leetcode solution 953 verification of alien dictionary. For more information about Go leetcode verification of alien dictionary, please pay attention to my other related articles!