題目分析

來(lái)源：acwing

分析：外部dfs，需要狀態(tài)恢復(fù)。
字符串a(chǎn)的后k的字母 和字符串b的前k個(gè)字母是否相同，用substr函數(shù)判斷：if(a.substr(a.size() - k, k) == b.substr(0,k))

ac代碼

#include<bits/stdc++.h> using namespace std; const int N = 30; int n; string words[N]; bool st[N][N]; int used[N];// 每個(gè)單詞用多少次 int g[N][N];// 兩個(gè)單詞重疊部分長(zhǎng)度的最小值 int ans; // 全局變量存的是結(jié)果//暴搜，求單詞接龍的長(zhǎng)度 // 龍，上一個(gè)單詞的編號(hào) void dfs(string dragon, int last){ans = max((int)dragon.size(), ans);// 長(zhǎng)度取最大值used[last] ++; // 用一次次數(shù)++for(int i = 0; i < n; i ++)// last--> i這個(gè)單詞可以連if(g[last][i] && used[i] < 2)// 這里substr(g[last][i])就是重疊部分后面的字符dfs(dragon + words[i].substr(g[last][i]), i);used[last] --;//回溯} int main(){cin >> n;for(int i = 0; i < n; i ++) cin >> words[i];char start;cin >> start;// 預(yù)處理，任意兩個(gè)單詞之間重疊的部分，存在g[][]數(shù)組中，存的是重疊部分的長(zhǎng)度for(int i= 0; i < n; i ++)for(int j = 0; j < n; j ++){string a = words[i], b = words[j];for(int k = 1; k < min(a.size(), b.size()); k ++)if(a.substr(a.size() - k, k) == b.substr(0,k)){g[i][j] = k;break;}}// 從起始字母開(kāi)始dfs，從words[i]這個(gè)單詞開(kāi)始搜，當(dāng)前用到的是第i個(gè)單詞for(int i = 0; i< n; i ++){if(words[i][0] == start)dfs(words[i], i);}cout << ans << endl;}

題目來(lái)源

https://www.acwing.com/problem/content/1119/

總結(jié)

以上是生活随笔為你收集整理的算法提高课-搜索-DFS之搜索顺序-AcWing 1117. 单词接龙：dfs的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。