算法
搜索,dfs
替换操作
字符串替换 主串从后向前遍历,子串从前向后,用substr
截取,相等就替换 然后一直搜下去。
这里有个小技巧
因为他给了开头字母,但是不能替换整个串,所以我们在开头字母前随便补一个字符。
然后丢到dfs
里,直接搜到最大值,最后答案减一即可。
还是能省一些代码的 ( | | )
#include<iostream>
using namespace std;
const int N = 25;
int n, ans;
string s[N];
int st[N];
void dfs(string x, int y)
{
st[y] ++;
int len = x.size();
ans = max(ans, len);
string t;
for(int i = 0; i < n; i ++)
for(int j = len - 1, k = 1; j > 0 && k < s[i].size(); j --, k ++)
{
if(st[i] < 2 && x.substr(j) == s[i].substr(0, k))
{
t = x.substr(0, len - k) + s[i];
dfs(t, i);
}
}
st[y] --;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
cin >> s[i];
string start;
cin >> start;
start = " " + start; // 在前面添加一个字符
dfs(start, n);
cout << ans - 1 << endl;
}
把接龙字符串拼接起来结算$ans$就容易多了,赞👍
# $ {\Huge 牜 \kern{-12pt}{𤛭}}$
太强了,ans-1这个想法很妙
为什么st++ st– 不能写在if里面
可以的啊,把外面的st去掉,里面变成st【i】++和st【i】–
还要把起点给回溯
噢噢 对
%%%
可以再解释下吗?
start = ” ” + start; // 在前面添加一个字符
加一个字符只是为了刚开始能执行for吗?
你理解一下题意,他给你的是一个开头字母 让你连,他的替换操作是
长度必须大于等于1,且严格小于两个串的长度
。所以如果要让开头就能替换的话,就需要多加一位。哦哦懂了谢谢
技巧妙啊
%%%
喜欢这写法。
%%%%%
saber代码!