算法问题实战策略 DICTIONARY
- 2019 年 10 月 27 日
- 筆記
地址 https://algospot.com/judge/problem/read/DICTIONARY
解法 构造一个26字母的有向图 判断无回路后 就可以输出判断出来的字符序了
比较各个字母的先后次序不必用一个单词分别同其他单词比较 只需要将临近的两个单词一一比较即可
证明如下
算法1 中判断有无回路 采取的是DFS方法
代码
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <algorithm> 5 #include <memory.h> 6 7 using namespace std; 8 9 /* 10 3 11 3 12 ba 13 aa 14 ab 15 5 16 gg 17 kia 18 lotte 19 lg 20 hanhwa 21 6 22 dictionary 23 english 24 is 25 ordered 26 ordinary 27 this 28 ====================================================== 29 INVALID HYPOTHESIS 30 ogklhabcdefijmnpqrstuvwxyz 31 abcdefghijklmnopqrstuvwxyz 32 */ 33 34 int n; 35 36 vector<pair<int, int>> vvmap; 37 38 void Compare(string s1, string s2) 39 { 40 int len = min(s1.size(),s2.size()); 41 42 for (int i = 0; i < len; i++) { 43 if (s1[i] == s2[i]) continue; 44 int a = s1[i] - 'a'; 45 int b = s2[i] - 'a'; 46 vvmap.push_back({a,b}); 47 break; 48 } 49 } 50 51 52 vector<int> seen, order; 53 54 void dfs(int here) { 55 seen[here] = 2; 56 for (int there = 0; there < 26; ++there) { 57 if ( find(vvmap.begin(),vvmap.end(),pair<int,int>(here,there)) != vvmap.end() 58 && seen[there] == 1 ) 59 dfs(there); 60 } 61 order.push_back(here); 62 } 63 64 vector<int> topologicalSort() 65 { 66 seen = vector<int>(26, 0); 67 for (int i = 0; i < vvmap.size(); i++) { 68 //记录需要dfs的索引 69 if (seen[vvmap[i].first] == 0) 70 seen[vvmap[i].first] =1; 71 if (seen[vvmap[i].second] == 0) 72 seen[vvmap[i].second] = 1; 73 } 74 order.clear(); 75 for (int i = 0; i < 26; i++) { 76 if (seen[i] == 1) 77 dfs(i); 78 } 79 80 reverse(order.begin(), order.end()); 81 82 for (int i = 0; i < order.size(); i++) { 83 for (int j = i+1; j < order.size(); j++) { 84 if (find(vvmap.begin(), vvmap.end(), pair<int, int>(order[j], order[i])) != vvmap.end()) 85 { 86 return vector<int>(); 87 } 88 } 89 } 90 return order; 91 } 92 93 94 int main() 95 { 96 cin >> n; 97 98 while (n--) { 99 int m; 100 vvmap.clear(); 101 cin >> m; 102 vector<string> vs; 103 for (int i = 0; i < m; i++) { 104 string s; 105 cin >> s; 106 vs.push_back(s); 107 } 108 109 for (int i = 0; i < vs.size()-1; i++) { 110 Compare(vs[i], vs[i + 1]); 111 } 112 113 vector<int> ans = topologicalSort(); 114 if (ans.empty()) { 115 cout << "INVALID HYPOTHESIS" << endl; 116 } 117 else { 118 for (int i = 0; i < 26; i++) { 119 if (find(ans.begin(), ans.end(), i) == ans.end()) { 120 ans.push_back(i); 121 } 122 } 123 124 for (int i = 0; i < ans.size(); i++) { 125 cout << (char)(ans[i] + 'a'); 126 } 127 cout << endl; 128 } 129 } 130 131 }
View Code
还可以以找欧拉回路的方法 判断字符序是否有无回路
todo
