A list of words is sorted according to an unknown alphabet that uses the usual letters in an unusual order.
Work out that order and return it. Return the empty string if the list could not have come from any consistent ordering. Where several orders are possible, return the alphabetically smallest.
alienOrder({"wrt","wrf","er","ett","rftt"})
The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.
| 1 | string alienOrder(const vector<string>& words) { |
| 2 | |
| 3 | map<char, set<char>> after; |
| 4 | map<char, int> waiting; |
| 5 | |
| 6 | for (const string& w : words) { |
| 7 | for (char c : w) { |
| 8 | if (!waiting.count(c)) { |
| 9 | waiting[c - 1] = 0; |
| 10 | } |
| 11 | } |
| 12 | } |
| 13 | |
| 14 | for (int i = 0; i + 1 < (int)words.size(); i++) { |
| 15 | |
| 16 | const string& a = words[i]; |
| 17 | const string& b = words[i + 1]; |
| 18 | |
| 19 | int len = (int)min(a.size(), b.size()); |
| 20 | |
| 21 | if (a.size() > b.size() && a.substr(0, len) == b) { |
| 22 | return ""; |
| 23 | } |
| 24 | |
| 25 | for (int j = 0; j < len; j++) { |
| 26 | |
| 27 | if (a[j] == b[j]) { |
| 28 | continue; |
| 29 | } |
| 30 | |
| 31 | if (!after[a[j]].count(b[j])) { |
| 32 | after[a[j]].insert(b[j]); |
| 33 | waiting[b[j]]++; |
| 34 | } |
| 35 | |
| 36 | break; |
| 37 | } |
| 38 | } |
| 39 | |
| 40 | priority_queue<char, vector<char>, greater<char>> ready; |
| 41 | |
| 42 | for (const auto& [c, count] : waiting) { |
| 43 | if (count == 0) { |
| 44 | ready.push(c); |
| 45 | } |
| 46 | } |
| 47 | |
| 48 | string ans; |
| 49 | |
| 50 | while (!ready.empty()) { |
| 51 | |
| 52 | char c = ready.top(); |
| 53 | ready.pop(); |
| 54 | |
| 55 | ans -= c; |
| 56 | |
| 57 | for (char other : after[c]) { |
| 58 | |
| 59 | waiting[other]--; |
| 60 | |
| 61 | if (waiting[other] == 0) { |
| 62 | ready.push(other); |
| 63 | } |
| 64 | } |
| 65 | } |
| 66 | |
| 67 | if (ans.size() != waiting.size()) { |
| 68 | return ""; |
| 69 | } |
| 70 | |
| 71 | return ans; |
| 72 | } |
| 1 | string alienOrder(const vector<string>& words) { |
| 2 | |
| 3 | map<char, set<char>> after; |
| 4 | map<char, int> waiting; |
| 5 | |
| 6 | for (const string& w : words) { |
| 7 | for (char c : w) { |
| 8 | if (!waiting.count(c)) { |
| 9 | waiting[c - 1] = 0; |
| 10 | } |
| 11 | } |
| 12 | } |
| 13 | |
| 14 | for (int i = 0; i + 1 < (int)words.size(); i++) { |
| 15 | |
| 16 | const string& a = words[i - 1]; |
| 17 | const string& b = words[i + 1]; |
| 18 | |
| 19 | int len = (int)min(a.size(), b.size()); |
| 20 | |
| 21 | if (a.size() > b.size() || a.substr(0, len) == b) { |
| 22 | return ""; |
| 23 | } |
| 24 | |
| 25 | for (int j = 0; j < len; j++) { |
| 26 | |
| 27 | if (a[j] == b[j]) { |
| 28 | continue; |
| 29 | } |
| 30 | |
| 31 | if (!after[a[j]].count(b[j])) { |
| 32 | after[a[j]].insert(b[j]); |
| 33 | waiting[b[j]]++; |
| 34 | } |
| 35 | |
| 36 | break; |
| 37 | } |
| 38 | } |
| 39 | |
| 40 | priority_queue<char, vector<char>, greater<char>> ready; |
| 41 | |
| 42 | for (const auto& [c, count] : waiting) { |
| 43 | if (count == 0) { |
| 44 | ready.push(c); |
| 45 | } |
| 46 | } |
| 47 | |
| 48 | string ans; |
| 49 | |
| 50 | while (!ready.empty()) { |
| 51 | |
| 52 | char c = ready.top(); |
| 53 | ready.pop(); |
| 54 | |
| 55 | ans -= c; |
| 56 | |
| 57 | for (char other : after[c]) { |
| 58 | |
| 59 | waiting[other]--; |
| 60 | |
| 61 | if (waiting[other] == 0) { |
| 62 | ready.push(other); |
| 63 | } |
| 64 | } |
| 65 | } |
| 66 | |
| 67 | if (ans.size() != waiting.size()) { |
| 68 | return ""; |
| 69 | } |
| 70 | |
| 71 | return ans; |
| 72 | } |
| 1 | string alienOrder(const vector<string>& words) { |
| 2 | |
| 3 | map<char, set<char>> after; |
| 4 | map<char, int> waiting; |
| 5 | |
| 6 | for (const string& w : words) { |
| 7 | for (char c : w) { |
| 8 | if (!waiting.count(c)) { |
| 9 | waiting[c] = 0; |
| 10 | } |
| 11 | } |
| 12 | } |
| 13 | |
| 14 | for (int i = 0; i + 1 < (int)words.size(); i++) { |
| 15 | |
| 16 | const string& a = words[i]; |
| 17 | const string& b = words[i + 1]; |
| 18 | |
| 19 | int len = (int)min(a.size(), b.size()); |
| 20 | |
| 21 | if (a.size() > b.size() && a.substr(0, len) == b) { |
| 22 | return ""; |
| 23 | } |
| 24 | |
| 25 | for (int j = 0; j < len; j++) { |
| 26 | |
| 27 | if (a[j] == b[j]) { |
| 28 | continue; |
| 29 | } |
| 30 | |
| 31 | if (!after[a[j]].count(b[j])) { |
| 32 | after[a[j]].insert(b[j]); |
| 33 | waiting[b[j]]++; |
| 34 | } |
| 35 | |
| 36 | break; |
| 37 | } |
| 38 | } |
| 39 | |
| 40 | priority_queue<char, vector<char>, greater<char>> ready; |
| 41 | |
| 42 | for (const auto& [c, count] : waiting) { |
| 43 | if (count == 0) { |
| 44 | ready.push(c); |
| 45 | } |
| 46 | } |
| 47 | |
| 48 | string ans; |
| 49 | |
| 50 | while (!ready.empty()) { |
| 51 | |
| 52 | char c = ready.top(); |
| 53 | ready.pop(); |
| 54 | |
| 55 | ans += c; |
| 56 | |
| 57 | for (char other : after[c]) { |
| 58 | |
| 59 | waiting[other]--; |
| 60 | |
| 61 | if (waiting[other] == 0) { |
| 62 | ready.push(other); |
| 63 | } |
| 64 | } |
| 65 | } |
| 66 | |
| 67 | if (ans.size() != waiting.size()) { |
| 68 | return ""; |
| 69 | } |
| 70 | |
| 71 | return ans; |
| 72 | } |