活跃农民-感谢提供高质量信息和讨论

- 积分
- 581
- 学分
- 个
- 大米
- 升
- 人参
- 枚
- 水井
- 尺
- 小麦
- 颗
- 萝卜
- 根
- 小米
- 粒
- UID
- 202381
- 注册时间
- 2016-1-10
- 最后登录
- 1970-1-1
- 在线时间
- 小时
- 好友
- 收听
- 听众
- 日志
- 相册
- 帖子
- 主题
- 分享
- 精华
|
- class Solution {
- public:
- string alienOrder(vector<string>& words) {
- if(words.size() == 1) return words[0];
- graph g = makeGraph(words);
- return sort(g);
- }
- private:-google 1point3acres
- typedef unordered_map<char, unordered_set<char>> graph;
-
- graph makeGraph(vector<string> words) {
- graph g;. 鍥磋鎴戜滑@1point 3 acres
- for(int i = 1; i < words.size(); ++i) {.1point3acres缃
- bool found = false;
. Waral 鍗氬鏈夋洿澶氭枃绔, - string word1 = words[i - 1];
- string word2 = words[i];
- int len1 = word1.size(), len2 = word2.size();
- int l = max(len1, len2);
- for(int j = 0; j < l; ++j) {
- if(j < len1 && g.find(word1[j]) == g.end()) {. from: 1point3acres.com/bbs
- g[word1[j]] = unordered_set<char>();.鏈枃鍘熷垱鑷1point3acres璁哄潧
- }
- if(j < len2 && g.find(word2[j]) == g.end()) {
- g[word2[j]] = unordered_set<char>();
-google 1point3acres - }
- if(j < len1 && j < len2 && word1[j] != word2[j] && found == false) {
- g[word1[j]].insert(word2[j]);
- found = true;. 鍥磋鎴戜滑@1point 3 acres
- }
- }
- }. more info on 1point3acres.com
- return g;. visit 1point3acres.com for more.
- }
- string sort(graph g) {
- string topo = "";
- vector<bool> visited(256, false), path(256, false);
- for(auto node : g) {
- if(!acyclic(g, node.first, visited, path, topo)) {
- return "";
- }
- }
- reverse(topo.begin(), topo.end());
- return topo;.鏈枃鍘熷垱鑷1point3acres璁哄潧
- }
-
- bool acyclic(graph g, char node, vector<bool> &visited, vector<bool> &path, string &topo) {
- if(path[node]) return false;
- if(visited[node]) return true;
- path[node] = visited[node] = true;
- for(auto n : g[node]) {. From 1point 3acres bbs
- if(!acyclic(g, n, visited, path, topo)) return false;
- }
- path[node] = false;
- topo.push_back(node);
- return true;
- }
-
- };
复制代码 |
|