题目描述
There is a new alien language that uses the English alphabet. However, the order among letters are unknown to you.
You are given a list of strings words from the dictionary, where words are sorted lexicographically by the rules of this new language.
Derive the order of letters in this language, and return it. If the given input is invalid, return “”. If there are multiple valid solutions, return any of them.
Constraints:
1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of only lowercase English letters.
样例
Example 1:
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Example 2:
Input: words = ["z","x"]
Output: "zx"
Example 3:
Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return "".
算法1
(拓扑排序) $O(n)$
建图:遍历所有单词将第一个不同字母设为边。
“wfc”, “wfa” 可得边 ‘c’ 到 ‘a’。由于使用了矩阵过滤掉重边。
注意如果有非法顺序例如 “abc”, “ab” 则直接返回无解。
所有其他出现但无顺序信息的字母标记为已出现(v),入度不更新。
建图完成后直接根据入度拓扑排序。(这里由于字母数固定为26省去了bfs队列)。
时间复杂度
C++ 代码
class Solution {
public:
int g[26][26], d[26];
bool v[26];
string alienOrder(vector<string>& words) {
memset(g, 0, sizeof g);
memset(d, 0, sizeof d);
memset(v, 0, sizeof v);
for (int i = 0; i < words.size(); i ++)
{
for (auto x : words[i]) v[x - 'a'] = true;
for (int j = i + 1; j < words.size(); j ++)
{
int k = 0;
for (auto x : words[j]) v[x - 'a'] = true;
while (k < words[i].size() && k < words[j].size() && words[i][k] == words[j][k]) k ++;
if (k < words[i].size() && k < words[j].size())
{
int a = words[i][k] - 'a', b = words[j][k] - 'a';
if (g[a][b] == 0)
{
g[a][b] = 1;
d[b] ++;
}
}
else if (k < words[i].size()) return "";
}
}
string res;
while (true)
{
bool hasNode = false;
for (int i = 0; i < 26; i ++)
{
if (v[i] && d[i] == 0)
{
res.push_back(i + 'a');
for (int j = 0; j < 26; j ++)
{
if (g[i][j]) d[j] --;
}
d[i] = -1;
hasNode = true;
}
}
if (!hasNode) break;
}
for (int i = 0; i < 26; i ++)
{
if (d[i] > 0) return "";
}
return res;
}
};