Leetcode 269 DFS

LC269_DFS.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]) {
        string result = "";
        result.push_back(a[i]);
        result.push_back(b[i]);
        return result;
      }
    }
    return "";
  }
  bool dfs(vector<unordered_set<char>>& graph, unordered_map<char, bool>& visited, unordered_set<char>& ancestors, char root, string& result) {
    if (ancestors.find(root) != ancestors.end()) {
      return false;
    }
    if (visited[root]) {
      return true;
    }
    unordered_set<char>& nextset = graph[root];
    visited[root] = true;
    ancestors.insert(root);
    for (char next : nextset) {
      bool valid = dfs(graph, visited, ancestors, next, result);
      if (!valid) {
        return false;
      }
    }
    result.push_back(root);
    return true;
  }
public:
  string alienOrder(vector<string>& words) {
    unordered_map<char, bool> visited;
    for (string& str : words) {
      for (char c : str) {
        visited[c] = false;
      }
    }
    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;
      }
      graph[diff[0]].insert(diff[1]);
    }
    string result = "";
    for (auto p : visited) {
      unordered_set<char> ancestors;
      bool valid = dfs(graph, visited, ancestors, p.first, result);
      if (!valid) {
        return "";
      }
    }
    reverse(result.begin(), result.end());
    return result;
  }
};