算法提高之单词接龙

• 核心思想：dfs

  • 预处理每两个字符串之间最短的公共部分长度

    • 求最短公共 最终字符串是最长
    • 

  • dfs所有开头字符串

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 25;
    
    int g[N][N];
    int n;
    string word[N];
    int used[N];
    int ans;
    
    void dfs(string dragon,int last)
    {
        ans = max((int)dragon.size(),ans);
        used[last] ++;
        for(int i=0;i<n;i++)
        {
            if(g[last][i] && used[i] < 2)  //last和i有公共部分
            {
                dfs(dragon+word[i].substr(g[last][i]),i);
            }
        }
        used[last]--;  //回溯
    }
    int main()
    {
        cin>>n;
        for(int i=0;i<n;i++) cin>>word[i];
        char start;
        cin>>start;
        
        for(int i=0;i<n;i++)  //预处理每两个字符串之间最短的公共部分长度
        {
            for(int j=0;j<n;j++)
            {
                string a = word[i],b=word[j];
                for(int k=1;k<min(a.size(),b.size());k++)
                {
                    if(a.substr(a.size()-k) == b.substr(0,k))
                    {
                        g[i][j] = k;
                        break;
                    }
                }
            }
        }
        for(int i=0;i<n;i++)
            if(word[i][0] == start)  //可以开头
                dfs(word[i],i);
                
        cout<<ans<<endl;
    }