Force deduction solution summary 953 verification of alien language dictionary

Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

Some alien languages also use small letters in English , But it may be in order order Different . The order of the alphabet （order） It's an arrangement of small letters .

Given a set of words written in alien language words, And the order of its alphabet order, Only when given words are arranged in dictionary order in this alien language , return true; otherwise , return false.

Example 1：

Input ：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output ：true
explain ： 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
explain ： In the alphabet of the language ,'d' be located 'l' after , that words[0] > words[1], Therefore, the word sequence is not arranged in dictionary order .
Example 3：

Input ：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output ：false
explain ： Current three characters "app" When the match , The second string is relatively short , Then according to the Dictionary Compilation Rules "apple" > "app", because 'l' > '∅', among '∅' It's white space , Defined as smaller than any other character （ For more information ）.
 

Tips ：

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/verifying-an-alien-dictionary
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  hold order Convert to char Corresponding to order map, Then compare them in pairs to see if they conform to the dictionary order .
*  In the process of comparison , Judge from front to back , Every judge ,
*  If index1>index2, It does not conform to the dictionary order ;
*  If index1<index2, In accordance with the dictionary order ;
*  If index1==index2 And not the last , Then judge the next ;
*  If index1==index2 And the last one , It does not conform to the dictionary order . such as apple,app.

Code ：

public class Solution953 {

    public boolean isAlienSorted(String[] words, String order) {
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = order.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            map.put(chars[i], i);
        }
        for (int i = 1; i < words.length; i++) {
            boolean str1Bigger = isStr1Bigger(words[i - 1], words[i], map);
            if (!str1Bigger) {
                return false;
            }
        }
        return true;
    }

    private boolean isStr1Bigger(String str1, String str2, Map<Character, Integer> map) {
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        for (int i = 0; i < chars1.length; i++) {
            if (i >= chars2.length) {
                return false;
            }
            int index1 = map.get(chars1[i]);
            int index2 = map.get(chars2[i]);
            if (index1 > index2) {
                return false;
            }
            if (index1 < index2) {
                return true;
            }
            continue;
        }
        return true;
    }

}