953. Verifying an Alien Dictionary
Intuition: The words are sorted lexicographically if and only if adjacent words are. This is because order is transitive: a <= b and b <= c implies a <= c.
Algorithm: Check whether all adjacent words a and b have a <= b.
(Referred to this post.)
Time = O(n), Space = O(1)
class Solution {
public boolean isAlienSorted(String[] words, String order) {
int[] map = new int[26];
for (int i = 0; i < order.length(); i++) {
map[order.charAt(i) - 'a'] = i;
}
outer:
for (int i = 0; i < words.length - 1; i++) {
String word1 = words[i];
String word2 = words[i + 1];
for (int j = 0; j < Math.min(word1.length(), word2.length()); j++) {
if (map[word1.charAt(j) - 'a'] < map[word2.charAt(j) - 'a']) {
continue outer;
} else if (map[word1.charAt(j) - 'a'] > map[word2.charAt(j) - 'a']) {
return false;
}
}
if (word1.length() > word2.length()) {
return false;
}
}
return true;
}
}