二刷 07/2022
Version #2 HashMap
Time O(MN)
Space O(26) ~ O(1)
class Solution {
public boolean isAlienSorted(String[] words, String order) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < order.length(); i++) {
map.put(order.charAt(i), i);
}
for (int i = 1; i < words.length; i++) {
if (!smaller(words[i - 1], words[i], map)) {
return false;
}
}
return true;
}
private boolean smaller(String a, String b, Map<Character, Integer> map) {
int pa = 0, pb = 0;
while (pa < a.length() && pb < b.length()) {
char ca = a.charAt(pa);
char cb = b.charAt(pb);
if (ca == cb) {
pa++;
pb++;
continue;
}
if (map.get(ca) < map.get(cb)) {
return true;
} else {
return false;
}
}
return a.length() <= b.length();
}
}
一刷
Version #1 Array as HashMap
Memory Usage: 37.3 MB, less than 94.58% of Java online submissions for Verifying an Alien Dictionary.
一开始想复杂了
其实只要比较相邻的word就可以了, 因为smaller than是transitive的
if a < b && b < c we can infer that a < c
Time O(word count * avg word length)
Space O(1)
class Solution {
public boolean isAlienSorted(String[] words, String order) {
char[] map = new char[26];
for (int i = 0; i < order.length(); i++) {
map[order.charAt(i) - 'a'] = (char)('a' + i);
}
String prev = null;
for (String word : words) {
if (prev != null && !smaller(prev, word, map)) {
return false;
}
prev = word;
}
return true;
}
private boolean smaller(String a, String b, char[] map) {
int i = 0;
for (i = 0; i < a.length() && i < b.length(); i++) {
char ca = map[a.charAt(i) - 'a'];
char cb = map[b.charAt(i) - 'a'];
if (ca != cb) {
return ca < cb;
}
// continue comparing if ca == cb
}
// apple
// app
if (i < a.length()) {
return false;
}
// Can be optimized to: return a.length() <= b.length()
return true;
}
}
No comments:
Post a Comment