Solution
The approach is to first create a map of alphabet -> ordering which we can use to compare any two alphabets in O(1) time. Then, we can compare two adjacent words at a time to see if they are in the correct order.
bool isAlienSorted(vector<string>& words, string order) {
unordered_map<char, int> m;
int i = 0;
for (char c : order)
m[c] = i++;
for (int i=0; i<words.size()-1; i++) {
string w1 = words[i];
string w2 = words[i+1];
if (compareWords(w1, w2, m) <= 0)
continue;
return false;
}
return true;
}
// helper function to check if two words are in the correct order
// this function is very similar to the "strcmp" function in C which is used to compare two strings
int compareWords (string w1, string w2, unordered_map<char, int> m) {
for (int i=0, j=0; i<w1.length() || j<w2.length(); i++, j++) {
if (i==w1.length())
return -1;
if (j==w2.length())
return 1;
if (w1[i]==w2[j])
continue;
if (m[w1[i]] > m[w2[j]])
return 1;
else
return -1;
}
return 0;
}
Time complexity: O(N) where N is the total number of characters