Leetcode--Java--953. 验证外星语词典

本文主要是介绍Leetcode--Java--953. 验证外星语词典，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

样例描述

示例 1：输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
输出：true
解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。
示例 2：输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
输出：false
解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。

思路

哈希数组 + 字符串模拟 + 传递性

由传递性，比较相邻的大小即可
哈希数组，或者用map来指示新规则
注意特殊情况，已经达到了短的长度，但是还没分出大小。

代码

class Solution {public boolean isAlienSorted(String[] words, String order) {int hash[] = new int[26];for (int i = 0; i < 26; i ++ ) {hash[order.charAt(i) - 'a'] = i;}//只需要比较每个相邻的是否有序，  由传递性 如果a <=b ，b <= c，则a <= cfor (int i = 0; i + 1 < words.length; i ++ ) {String s1 = words[i];String s2 = words[i + 1];int m = s1.length(), n = s2.length();//标志是否要继续比较， （直到比较出高下 才停止比较）boolean flag = true; for (int k = 0; k < Math.min(m ,n) && flag; k ++ ) {//如果不相同才比较，一直相同就直接遍历if (s1.charAt(k) != s2.charAt(k)) {//如果逆序if (hash[s1.charAt(k) - 'a'] > hash[s2.charAt(k) - 'a']) {return false;}//否则就是正序，说明符合规则，同时也表明比较出了高下else flag = false;}}//特判：对于[app, apple]这种，比较完了还没出高下，flag依旧trueif (flag && m > n) {return false;}}return true;}
}