算法问题实战策略 WORDCHAIN

地址 https://algospot.com/judge/problem/read/WORDCHAIN

解答:

1 书上的解法是制作有向图然后查找欧拉回路代码实现稍后

假设一定存在欧拉路径的做法

  1 #include <iostream>
  2 #include <vector>
  3 #include <string>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 vector<vector<int>> adj;
  9 
 10 vector<string> graph[26][26];
 11 
 12 vector<int> indegree, outdegree;
 13 
 14 void makeGraph(const vector<string>& words)
 15 {
 16     for (int i = 0; i < 26; i++)
 17         for (int j = 0; j < 26; j++)
 18             graph[i][j].clear();
 19     adj = vector<vector<int>>(26, vector<int>(26, 0));
 20     indegree = outdegree = vector<int>(26, 0);
 21     for (int i = 0; i < words.size(); i++) {
 22         int a = words[i][0] - 'a';
 23         int b = words[i][words[i].size() - 1] - 'a';
 24         graph[a][b].push_back(words[i]);
 25         adj[a][b]++;
 26         outdegree[a]++;
 27         indegree[b]++;
 28     }
 29 }
 30 
 31 void getEulerCircuit( int here,vector<int>& circuit )
 32 {
 33     for (int there = 0; there < adj.size(); ++there) {
 34         while (adj[here][there] > 0) {
 35             adj[here][there]--;
 36             getEulerCircuit(there, circuit);
 37         }
 38     }
 39 
 40     circuit.push_back(here);
 41 }
 42 
 43 vector<int> getEulerTrailOrCircuit()
 44 {
 45     vector<int> circuit;
 46 
 47     for (int i = 0; i < 26; i++) {
 48         if (outdegree[i] == indegree[i] + 1) {
 49             getEulerCircuit(i, circuit);
 50             return circuit;
 51         }
 52     }
 53 
 54     for (int i = 0; i < 26; ++i)
 55     {
 56         if (outdegree[i]) {
 57             getEulerCircuit(i, circuit);
 58             return circuit;
 59         }
 60     }
 61 
 62     return circuit;
 63 }
 64 
 65 string solve(const vector<string>& words)
 66 {
 67     makeGraph(words);
 68 
 69     vector<int> circuit = getEulerTrailOrCircuit();
 70 
 71     if (circuit.size() != words.size() + 1) return "IMPOSSIBLE";
 72 
 73     reverse(circuit.begin(), circuit.end());
 74     string ret;
 75     for (int i = 1; i < circuit.size(); i++) {
 76         int a = circuit[i - 1], b = circuit[i];
 77         if (ret.size()) ret += " ";
 78         ret += graph[a][b].back();
 79         graph[a][b].pop_back();
 80     }
 81 
 82     return ret;
 83 }
 84 
 85 int n, m;
 86 int main()
 87 {
 88     cin >> n;
 89     while (n--) {
 90         cin >> m;
 91         vector<string> words;
 92         while (m--) {
 93             string s;
 94             cin >> s;
 95             words.push_back(s);
 96         }
 97 
 98         cout << solve(words) << endl;
 99 
100     }
101 
102     return 0;
103 }

View Code

先统计有向图的出入度判断有无欧拉回路与欧拉路径后在进行dfs的做法

  1 #include <iostream>
  2 #include <vector>
  3 #include <string>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 vector<vector<int>> adj;
  9 
 10 vector<string> graph[26][26];
 11 
 12 vector<int> indegree, outdegree;
 13 
 14 void makeGraph(const vector<string>& words)
 15 {
 16     for (int i = 0; i < 26; i++)
 17         for (int j = 0; j < 26; j++)
 18             graph[i][j].clear();
 19     adj = vector<vector<int>>(26, vector<int>(26, 0));
 20     indegree = outdegree = vector<int>(26, 0);
 21     for (int i = 0; i < words.size(); i++) {
 22         int a = words[i][0] - 'a';
 23         int b = words[i][words[i].size() - 1] - 'a';
 24         graph[a][b].push_back(words[i]);
 25         adj[a][b]++;
 26         outdegree[a]++;
 27         indegree[b]++;
 28     }
 29 }
 30 
 31 void getEulerCircuit(int here, vector<int>& circuit)
 32 {
 33     for (int there = 0; there < adj.size(); ++there) {
 34         while (adj[here][there] > 0) {
 35             adj[here][there]--;
 36             getEulerCircuit(there, circuit);
 37         }
 38     }
 39 
 40     circuit.push_back(here);
 41 }
 42 
 43 
 44 string solve(const vector<string>& words)
 45 {
 46     makeGraph(words);
 47 
 48     int start = -1; int end = -1;
 49 
 50     for (int i = 0; i < 26; i++) {
 51         if (outdegree[i] != indegree[i]) {
 52             if (outdegree[i] == indegree[i] + 1 ) {
 53                 if (-1 == start)
 54                     start = i;
 55                 else
 56                     return "IMPOSSIBLE";
 57             }
 58             else if (outdegree[i] + 1 == indegree[i] ) {
 59                 if( -1 == end)
 60                     end = i;
 61                 else
 62                     return "IMPOSSIBLE";
 63             }
 64         }
 65     }
 66 
 67     vector<int> circuit;
 68     if (start == -1 && end == -1) {
 69         for (int i = 0; i < 26; ++i)
 70         {
 71             if (outdegree[i]) {
 72                 getEulerCircuit(i, circuit);
 73                 break;
 74             }
 75         }
 76     }
 77     else {
 78         getEulerCircuit(start, circuit);
 79     }
 80 
 81 
 82     reverse(circuit.begin(), circuit.end());
 83     string ret;
 84     for (int i = 1; i < circuit.size(); i++) {
 85         int a = circuit[i - 1], b = circuit[i];
 86         if (ret.size()) ret += " ";
 87         ret += graph[a][b].back();
 88         graph[a][b].pop_back();
 89     }
 90 
 91     return ret;
 92 }
 93 
 94 int n, m;
 95 int main()
 96 {
 97     cin >> n;
 98     while (n--) {
 99         cin >> m;
100         vector<string> words;
101         while (m--) {
102             string s;
103             cin >> s;
104             words.push_back(s);
105         }
106 
107         cout << solve(words) << endl;
108 
109     }
110 
111     return 0;
112 }

View Code

2 个人觉得可以使用首尾单词作为关键字去哈希然后进行哈希查找与DFS结合的搜索看看最后能否将单词全部使用代码如下

TLE

  1 #include <iostream>
  2 #include <vector>
  3 #include <string>
  4 
  5 
  6 using namespace std;
  7 
  8 int n, m;
  9 
 10 /*
 11 3
 12 4
 13 dog
 14 god
 15 dragon
 16 need
 17 3
 18 aa
 19 ab
 20 bb
 21 2
 22 ab
 23 cd
 24 
 25 
 26 need dog god dragon
 27 aa ab bb
 28 IMPOSSIBLE
 29 */
 30 
 31 vector<string> ret;
 32 
 33 void Dfs( int begIdx,vector<vector<vector<string>>>& vvstr)
 34 {
 35     if (ret.size() == m) {
 36         return;
 37     }
 38 
 39     for (int i = 0; i < 26; i++) {
 40         for (int j = 0; j < vvstr[begIdx][i].size(); j++) {
 41             //选择 nextBegIdx 开头的字母
 42             //如果已经选择过了 则进行下一次尝试
 43             if (vvstr[begIdx][i][j][0] == '#') 
 44                 continue;
 45 
 46             //开始选择该单词接龙
 47             int nextBegIdx = vvstr[begIdx][i][j].back() - 'a';
 48             ret.push_back(vvstr[begIdx][i][j]);
 49             vvstr[begIdx][i][j][0] = '#'; //修改字符串的第一个字符 作为已经被选择的标记
 50         
 51             Dfs( nextBegIdx, vvstr);
 52 
 53             if (ret.size() == m) {
 54                 return;
 55             }
 56 
 57             vvstr[begIdx][i][j][0] = 'a'+ begIdx;
 58             ret.pop_back();
 59             break;
 60         }
 61     }
 62 
 63 }
 64 
 65 
 66 void DfsStart(vector<vector<vector<string>>>& vvstr)
 67 {
 68     for (int i = 0; i < 26; i++) {
 69         for (int j = 0; j < 26; j++) {
 70             for (int k = 0; k < vvstr[i][j].size(); k++) {
 71                 //选中这个单词作为开始
 72                 int nextBegIdx = vvstr[i][j][k].back() - 'a';
 73                 ret.push_back(vvstr[i][j][k]);
 74                 vvstr[i][j][k][0] = '#'; //修改字符串的第一个字符 作为已经被选择的标记
 75                 Dfs( nextBegIdx,vvstr);
 76 
 77                 if (ret.size() == m) {
 78                     return;
 79                 }
 80 
 81                 //复原 继续下一次选择
 82                 vvstr[i][j][k][0] = 'a'+i;
 83                 ret.pop_back();
 84                 break;
 85             }
 86         }
 87     }
 88 
 89 }
 90 
 91 
 92 int main()
 93 {
 94     cin >> n;
 95     while (n--) {
 96         cin >> m;
 97         string s; vector<vector<vector<string>>> vvstr(26, vector<vector<string>>(26, vector<string>()));
 98         ret.clear();
 99         for (int i = 0; i < m; i++){
100             cin >> s;
101             int beg = s[0] - 'a';
102             int end = s.back() - 'a';
103             vvstr[beg][end].push_back(s);
104         }
105         DfsStart(vvstr);
106         if(!ret.empty()){
107             for (int i = 0; i < ret.size(); i++) {
108                 cout << ret[i] << " ";
109             }
110         }
111         else {
112             cout << "IMPOSSIBLE";
113         }
114         cout << endl;
115     }
116 
117     return 0;
118 }

View Code

作者: itdef
欢迎转帖请保持文本完整并注明出处
技术博客 http://www.cnblogs.com/itdef/
B站算法视频题解
https://space.bilibili.com/18508846
qq 151435887
gitee https://gitee.com/def/
欢迎c c++ 算法爱好者 windows驱动爱好者服务器程序员沟通交流
如果觉得不错，欢迎点赞，你的鼓励就是我的动力
阿里打赏