1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public boolean isAlienSorted(String[] words, String order) {
Map<Character, Integer> orderMap = new HashMap<>();
for (int i = 0; i < order.length(); i++) {
orderMap.put(order.charAt(i), i);
}
for (int i = 1; i < words.length; i++) {
if (compare(words[i - 1], words[i], orderMap) > 0)
return false;
}
return true;
}
private int compare(String str1, String str2, Map<Character, Integer> orderMap) {
if (str1.equals(str2))
return 0;
int ptr1 = 0, ptr2 = 0;
while (ptr1 < str1.length() && ptr2 < str2.length()) {
int letterOneOrder = orderMap.get(str1.charAt(ptr1)), letterTwoOrder = orderMap.get(str2.charAt(ptr2));
if (letterOneOrder < letterTwoOrder) {
return -1;
} else if (letterOneOrder > letterTwoOrder) {
return 1;
} else {
ptr1 += 1;
ptr2 += 1;
}
}
return ptr1 == str1.length() ? -1 : 1;
}
}
|
我们要思考两个string是如何比较大小的. 是一个一个char进行比较的. 直到某个位置发现一个char大一个char小. 那么就会有下面的情况: 在其中一个string用完之前分出大小: 在某个位置, 一个string的char比另一个string该位置的char小. 在其中一个string用完后也没分出大小, 也就是短的string是长的string的substring. 此时看长的string的长度. 如果长的string刚刚好也用完(此时叫长的string不是很合适了), 那么这两个string就是相等的, 否则短的string小,
长的string大.
因此按照这个逻辑一个一个char比较即可.
时间复杂度: O(ns) 因为我们要遍历每一个word的每一个char
空间复杂度: O(1) 用来记录order的map
