算法与数据结构|P1019 单词接龙（字符串 DFS 回溯）算法与数据结构|洛谷

题的链接：P1019 单词接龙
题解：

相邻部分不能有包含关系，有歧义。。。例如，as 和 asdf，后面不能包含前面，但是前面能包含后面，并且若前后相同例如 elve 和 elve 则是可以连接的。这样解决包含问题：

if(b.find(a) != string::npos && b != a) return false;

最复杂就是这里：判断能否连接，用for循环从后往前截取字符串 a ，再用 b 去找 t ，用 flag 标记是否找到，找到即return true, 否则继续截取字符串直到截取完若是还没有找到则彻底找不到，退出循环返回false.

【算法与数据结构|P1019 单词接龙（字符串 DFS 回溯）】不能单纯的这样去判断，要严谨的一个一个对应的去比较：

if(b.find(t) != string::npos && t[0] == b[0]) return true;

正确的check函数：

for(int i = a.size() - 1; i >= 0; i--) { int flag = 1; t = a.substr(i); for(int j = 0; j < t.size(); j++) if(t[j] != b[j]) {flag = 0; break; } if(flag) return true; } return false;

若能连接，则调用连接函数，将 b 中与 a 重复的最小部分去掉和 a 相加即可。

void connect(string &a, string b) { a += b.substr(t.size()); }

DFS函数，将所有情况遍历一遍，走到头就回溯一次，判断条件 if(vis[i] >= 2) continue; 因为每个字符串最多可以用两次，每次更新一下当前最大长度即可。。。要用到副本 ss ，原因见下面写的注意！

void dfs(string s) { maxLen = max((int)s.size(), maxLen); for(int i = 0; i < N; i++) { if(vis[i] >= 2) continue; if(check(s, str[i])) { string ss = s; connect(ss, str[i]); vis[i]++; dfs(ss); vis[i]--; } } }

注意：这样是不行的，会发现 s 被修改后，回溯时是无法变回原来的值，原串改变就无法回溯了，所以要用一个副本来保存 s ，这样才可以正确的回溯。。。

if(check(s, str[i])) { connect(s, str[i]); vis[i]++; dfs(s); vis[i]--; }

主函数，要找到起始位置，标记用过，结束后取消标记。

for(int i = 0; i < N; i++) { if(c == str[i][0]) { vis[i]++; dfs(str[i]); vis[i]--; } }

参考代码：带有注释和错误思路版本。。。

#include #include #include #include using namespace std; int N, maxLen; string str[100], t; char c; int vis[100]; /* 1 envelope e */bool check(string a, string b)//1、atactactouch choose { //if(a == b) return true; if(b.find(a) != string::npos && b != a) return false; //if(a.find(b)!=string::npos || b.find(a)!=string::npos) return false; for(int i = a.size() - 1; i >= 0; i--) { int flag = 1; t = a.substr(i); //if(b.find(t) != string::npos && t[0] == b[0]) return true; //if(b.find(t) != string::npos) //{ for(int j = 0; j < t.size(); j++) //if(t[j] != b[j]) break; if(t[j] != b[j]) {flag = 0; break; } //return true; //} if(flag) return true; } return false; }void connect(string &a, string b) { a += b.substr(t.size()); }void dfs(string s) { maxLen = max((int)s.size(), maxLen); for(int i = 0; i < N; i++) { if(vis[i] >= 2) continue; if(check(s, str[i])) { //connect(s, str[i]); //cout << s << endl; //vis[i]++; //dfs(s); //vis[i]--; string ss = s; connect(ss, str[i]); //cout << ss << endl; vis[i]++; dfs(ss); vis[i]--; } } }int main() { cin >> N; for(int i = 0; i < N; i++) cin >> str[i]; cin >> c; for(int i = 0; i < N; i++) { if(c == str[i][0]) { vis[i]++; dfs(str[i]); vis[i]--; } } cout << maxLen << endl; //cout << check("atactactouch", "choose") << endl; //cout << check("envelope", "envelope") << endl; return 0; }

参考代码：没有注释，简洁版本。。。

#include #include #include #include using namespace std; int N, maxLen; string str[100], t; char c; int vis[100]; bool check(string a, string b) { if(b.find(a) != string::npos && b != a) return false; for(int i = a.size() - 1; i >= 0; i--) { int flag = 1; t = a.substr(i); for(int j = 0; j < t.size(); j++) if(t[j] != b[j]) {flag = 0; break; } if(flag) return true; } return false; }void connect(string &a, string b) { a += b.substr(t.size()); }void dfs(string s) { maxLen = max((int)s.size(), maxLen); for(int i = 0; i < N; i++) { if(vis[i] >= 2) continue; if(check(s, str[i])) { string ss = s; connect(ss, str[i]); vis[i]++; dfs(ss); vis[i]--; } } }int main() { cin >> N; for(int i = 0; i < N; i++) cin >> str[i]; cin >> c; for(int i = 0; i < N; i++) { if(c == str[i][0]) { vis[i]++; dfs(str[i]); vis[i]--; } } cout << maxLen << endl; return 0; }