这道题是炫姐推荐给我的，用到了哈希表和验证字母序，比较有意思。
首先，需要使用一个哈希表（因为字母数是定的，所以这里可以使用一个数组作为哈希表）来存入外星字母的顺序（因为计算机中的字母以 ASCII 码存放，所以我们需要用这个哈希表将这个转换为另一种顺序）。
接下来，就是到了验证字母序的部分，首先，如果 vector 中的所有单词都符合字母序，那么相邻的两个单词必须符合字母序，所以这个问题就转换为验证相邻两个单词是否符合字母序的问题了。在比较字母序的时候，如果两个单词中前一个单词中某个字母的顺序大于后一个单词，则验证失败，如果小于，则验证成功，如果相等，则比较后面的字母。如果全部比较完以后，还是未得到结果，就说明两个单词重合部分是一样的，现在就要看看单词的长短，比较长的单词肯定字母序会更大，所以由此可以得到结果。
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
| class Solution {
public:
bool isAlienSorted(vector<string>& words, string order) {
if(words.size()<=1) return true;
for(int i=0;i<order.size();i++){
alphaTable[order[i]-'a']=i;
}
for(int i=1;i<words.size();i++){
if(!verify(words[i-1],words[i])) return false;
}
return true;
}
private:
int alphaTable[26];
bool verify(string& word1,string& word2){
int len=min(word1.size(),word2.size());
for(int i=0;i<len;i++){
int pos1=alphaTable[word1[i]-'a'];
int pos2=alphaTable[word2[i]-'a'];
if(pos1<pos2) return true;
else if(pos1>pos2) return false;
}
if(word1.size()>word2.size()) return false;
else return true;
}
};
|