Problem
In an alien language, surprisingly they also use english lowercase letters, but possiblyĀ in a differentĀ order
. TheĀ order
Ā of the alphabetĀ is some permutationĀ of lowercase letters.
Given a sequence ofĀ words
Ā written in the alien language,Ā and theĀ order
Ā of the alphabet,Ā returnĀ true
Ā if and only if the givenĀ words
Ā are sorted lexicographicaly in this alien language.
Example 1:
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" Output: true Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.
Example 2:
Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz" Output: false Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.
Example 3:
Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz" Output: false Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > 'ā ', where 'ā ' is defined as the blank character which is less than any other character (More info).
Note:
1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
- All characters inĀ
words[i]
Ā andĀorder
Ā are english lowercase letters.
Solution: Hashtable
Time complexity: O(sum(len(words[i])))
Space complexity: O(26)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua, 8 ms class Solution { public: bool isAlienSorted(vector<string>& words, string order) { vector<char> m(26); for (int i = 0; i < 26; ++i) m[order[i] - 'a'] = 'a' + i; for (int i = 0; i < words.size(); ++i) { for (int j = 0; j < words[i].length(); ++j) words[i][j] = m[words[i][j] - 'a']; if (i > 0 && words[i] < words[i - 1]) return false; } return true; } }; |