AcWing 1117. 单词接龙

题目传送门

• 为了不完整匹配给定的第一个输入字符，给字符前面拼了一个空格。
• 为了不完整匹配给的字符串，所以遍历长串不能到j=0
• 因为最开始多拼了一个空格，所以最终的答案需要减1.
• 字符串的截取操作练习
• 常规\(dfs\)

#include 

using namespace std;
const int N = 25;
/**
字符串替换 主串从后向前遍历，子串从前向后，用substr截取，相等就替换 然后一直搜下去。
这里有个小技巧
因为他给了开头字母，但是不能替换整个串，所以我们在开头字母前随便补一个字符。
然后丢到dfs里，直接搜到最大值，最后答案减一即可。
还是能省一些代码的
 */
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++) { //枚举每个字符串
        //双指针 j:主串从后向前遍历,k:子串从前向后

        //注意这里j>0,而不是j>=0
        //因为题目要求：“且严格小于两个串的长度，例如 at 和 atide 间不能相连。”
        //为了处理逻辑一致，所的在起始字符前面加了一个空格
        if (st[i] >= 2) continue;
        for (int j = len - 1, k = 1; j > 0 && k < s[i].size(); j--, k++) {
            //如果第i个字符串使用了0,1两次，那么不能继续使用
            //如果主串的后缀和子串的前缀一样
            if (x.substr(j) == s[i].substr(0, k)) {
                //拼接出一个新串
                t = x.substr(0, len - k) + s[i];
                //接龙这个新串
                dfs(t, i);
                //如果发现了短的，就没必要继续尝试其它的子串对比了，因为现在的对比方法是找到了最短的匹配，这样的接龙长度最长
                //当然，也可以继续，但一定是无用的，空跑的，需要剪枝的
                break;
            }
        }
    }
    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);           // 这个n 用的妙，正常的字符串都是0~n-1,把这个空格当做了第n个，还不能用的太大，否则数组越界
    cout << ans - 1 << endl; // 多加了一个空格，最后-1
    return 0;
}