There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Example 1:
Input:
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
Output: "wertf"
Example 2:
Input:
[
"z",
"x"
]
Output: "zx"
Example 3:
Input: [ "z", "x", "z" ] Output:""Explanation: The order is invalid, so return"".
Note:
- You may assume all letters are in lowercase.
- You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
- If the order is invalid, return an empty string.
- There may be multiple valid order of letters, return any one of them is fine.
class Solution {
public:
void makeGraph(string first, string second, map<char, set<char>>& graph) {
int len = min(first.size(), second.size());
if (len == 0) {
return;
}
for (int i = 0; i < len; i++) {
if (first[i] != second[i]) {
graph[first[i]].insert(second[i]);
return;
}
}
}
void toposort(map<char, set<char>>& graph, string& ans) {
if (graph.size() == 0) {
return;
}
vector<int> visited(26, 0);
bool isCycle = false;
for (auto node : graph) {
dfs(graph, node.first, ans, visited, isCycle);
}
if (isCycle) {
ans = "";
}
return;
}
void dfs(map<char, set<char>>& graph, char node, string& ans,
vector<int>& visited, bool& isCycle) {
if (visited[node - 'a'] == 2) {
return;
}
// It means cycle is detected and graph is not valid.
if (visited[node - 'a'] == 1) {
isCycle = true;
return;
}
visited[node - 'a'] = 1;
for (auto neighbor : graph[node]) {
dfs(graph, neighbor, ans, visited, isCycle);
}
visited[node - 'a'] = 2;
ans = node + ans;
}
string alienOrder(vector<string>& words) {
map<char, set<char>> graph;
string ans;
if (words.size() == 0) {
return ans;
} else if (words.size() == 1) {
return words[0];
}
for (auto word : words) {
for (auto ch : word) {
graph[ch] = {};
}
}
for (int i = 1; i < words.size(); i++) {
makeGraph(words[i - 1], words[i], graph);
}
toposort(graph, ans);
return ans;
}
};
========= Next time ========
class Solution {
public:
string alienOrder(vector<string>& words) {
string ans;
unordered_map<char, unordered_set<char>> graph;
bool valid = prepareGraph(words, graph);
if (!valid) {
return "";
}
valid = toposort(graph, ans);
if (!valid) {
return "";
}
return ans;
}
bool prepareGraph(vector<string>& words, unordered_map<char, unordered_set<char>>& graph) {
for (auto word: words) {
for (auto ch : word) {
graph[ch] = {};
}
}
for (int i = 0; i < words.size() - 1; i++) {
string first = words[i], second = words[i + 1];
int size = min(first.size(), second.size());
for (int j = 0; j < size; j++) {
if (first[j] != second[j]) {
graph[first[j]].insert(second[j]);
break;
} else if (j == size - 1) {
if (size != first.size()) {
return false;
}
}
}
}
return true;
}
bool toposort(unordered_map<char, unordered_set<char>>& graph, string& ans) {
unordered_map<char, int> visited;
for (int i = 0; i < 26; i++) {
char node = 'a' + i;
visited[node] = 0;
}
for (auto entry : graph) {
if (visited[entry.first] == 0) {
if (!dfs(entry.first, graph, visited, ans)) {
return false;
}
}
}
return true;
}
bool dfs(char node, unordered_map<char, unordered_set<char>>& graph,
unordered_map<char, int>& visited, string& ans) {
if (visited[node] == 2) {
return true;
}
if (visited[node] == 1) {
return false;
}
visited[node] = 1;
for (auto neighbor : graph[node]) {
if (!dfs(neighbor, graph, visited, ans)) {
return false;
}
}
visited[node] = 2;
ans = string(1, node) + ans;
return true;
}
};
No comments:
Post a Comment