Closed bitfishxyz closed 5 years ago
/**
* 单词数组中,所有单词相同索引位置的字母都是按照字典序的就行。
*/
class Solution {
public boolean isAlienSorted(String[] words, String order) {
Map<Character, Integer> priorityMap = priority(order);
/**
* 定义一个二维数组
* - 第一个维度表示数组中某一单词的索引。
*
* characters[0] 代表所有字符串索引为0的位置的字母的列表
* 它是一个长度为words.length的数组
*
* - 第二个维度就是这一索引下,所有的字符
*
* 长度不够,用null代替
*/
Character[][] characters = new Character[20][100];
for (int i = 0; i < 20; i++) {
for (int j = 0; j < words.length; j++) {
characters[i][j] = words[j].length() >= i + 1 ? words[j].charAt(i) : null;
}
}
/**
* 这里的逻辑出错了
* - 只要第一个字母小一点,后面的不用比较,
* 否者需要比较后面的。。
*/
for (int i = 0; i < 20; i++) {
if (!isOrder(characters[i], priorityMap)){
return false;
}
}
return true;
}
private boolean isOrder(Character[] chars, Map<Character, Integer> priorityMap){
if (chars.length <= 1) {
return true;
}
for (int i = 0; i < chars.length - 1; i++) {
// 存在不符合要求,就返回false
if (!isOrder(chars[i], chars[i + 1], priorityMap)){
return false;
}
}
return true;
}
/**
* 获得在这行外星文中,每个字母的优先级
* 优先级越低,在字典中越靠前
* @param order
* @return
*/
private Map<Character, Integer> priority(String order){
Map<Character, Integer> priorityMap = new HashMap<>();
for (int i = 0; i < order.length(); i++) {
// 每个字母的优先级,就是它在这个字符串中的顺序
priorityMap.put(order.charAt(i), i);
}
return priorityMap;
}
/**
* 判断c1的字典序是不是在c2前面
* @param c1
* @param c2
* @param priorityMap
* @return
*/
private boolean isOrder(Character c1, Character c2,
Map<Character, Integer> priorityMap){
// 二维数组中会有很多null,这种写法就是忽略null
if (c1 == null || c2 == null) {
return true;
}
return priorityMap.get(c1) <= priorityMap.get(c2);
}
public static void main(String[] args) {
Solution solution = new Solution();
String[] words = new String[3];
words[0] = "word";
words[1] = "world";
words[2] = "row";
String order = "worldabcefghijkmnpqstuvxyz";
System.out.println(solution.isAlienSorted(words, order));
String[] words2 = new String[2];
words2[0] = "hello";
words2[1] = "leetcode";
String order2 = "hlabcdefgijkmnopqrstuvwxyz";
System.out.println(solution.isAlienSorted(words2, order2));
}
}
某种外星语也使用英文小写字母,但可能顺序 order 不同。字母表的顺序(order)是一些小写字母的排列。
给定一组用外星语书写的单词 words,以及其字母表的顺序 order,只有当给定的单词在这种外星语中按字典序排列时,返回 true;否则,返回 false。
示例 1:
示例 2:
示例 3:
提示: