Leetcode 269 BFS

LC269_BFS.cpp

class Solution {
private:
  string compare(string& a, string& b) {
    int n = min(a.length(), b.length());
    for (int i = 0; i < n; ++i) {
      if (a[i] != b[i]) {
        return {a[i], b[i]};
      }
    }
    return "";
  }
public:
  string alienOrder(vector<string>& words) {
    unordered_map<char, int> indegrees;
    for (string& str : words) {
      for (char c : str) {
        indegrees[c] = 0;
      }
    }
    int targetSize = indegrees.size();
    vector<unordered_set<char>> graph(256);
    for (int i = 1; i < words.size(); ++i) {
      string diff = compare(words[i - 1], words[i]);
      if (diff == "") {
        continue;
      }
      if (graph[diff[0]].find(diff[1]) == graph[diff[0]].end()) {
        indegrees[diff[1]]++;
        graph[diff[0]].insert(diff[1]);
      }
    }
    queue<char> q;
    for (auto p : indegrees) {
      if (p.second == 0) {
        q.push(p.first);
      }
    }
    string result = "";
    while (!q.empty()) {
      char front = q.front();
      result += front;
      q.pop();
      auto& nextset = graph[front];
      for (char next : nextset) {
        indegrees[next]--;
        if (indegrees[next] == 0) {
          q.push(next);
        }
      }
    }
    return result.length() == targetSize ? result : "";
  }
};