算法提高课汇总

算法思路

• 顺序: 每次遍历与当前单词能够接龙的单词.

• 重合部分长度可任意选择, 由于任意选择构成的单词串对后续单词的连接没有影响,
  而题目求最大长度, 所以每次选重合长度最小的方案.

具体实现

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25;

int n, ans;
string word[N];
int g[N][N]; //g[i][j] = 0: 单词i, j不能连接; = x:重合的最小长度为x
int used[N]; //使用次数

void dfs(string dragon, int index)
{
    ans = max(ans, int(dragon.size()));

    used[index] ++ ;

    for ( int i = 0; i < n; i ++ )
    {
        if ( g[index][i] && used[i] < 2 )
            dfs(dragon + word[i].substr(g[index][i]), i);
    }

    used[index] -- ;
}

int main()
{
    char start;
    cin >> n;
    for ( int i = 0; i < n; i ++ )  cin >> word[i];
    cin >> start;

    //预处理单词i可以连接的单词 计算最小重合部分
    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, 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;

    return 0;
}