词链

· · 题解

updated:2020.10.30

（把之前的一些明显的错误改了，我果然还是学艺不精。。）

首先我们知道：如果字符串A的尾部等于字符串B的头部，那么说明这两个字符串是有可能相连的。

数据范围并不是很大，我们可以考虑用搜索的策略。

关键是要找到一个准确的起点来搜索

那么起点是哪个字符串呢？

我们可以来仔细分析一下：如果假设有字符串abs和字符串sto这两个字符串。他们相连后就是abs.sto。

我们发现，每个点两边的字母一定是相同的。那对于整条链来说，如果除去最左端和最右端的两个字母后。中间的每个点两边的字母都相同，也就有了以下两个很重要的性质：

１每个字母出现的次数一定是偶数次

２每个字符出现在字符串首位的个数一定等于出现在字符串末尾的个数（因为对于任何一个点，都能满足上面的条件）

现在将左端和右端的两个字母考虑进去，一定会出现以下两种情况中的一种

１左端和右端的两个字母相同，上面的两个性质仍然成立，此时我们将字典序最小的那个字符串作为起点。

２左端和右端的两个字符不同，上面两个性质不再成立，但是又有了新的性质：

（１）一定有一个字母，其出现在字符串首位的个数等于出现在字符串末尾的个数＋１，这个字母一定作起点（设为c）。

（２）一定还有一个字母，其出现在字符串首位的个数等于出现在字符串末尾的个数－１，这个字母一定作终点（设为d）。我们在以ｃ为首的字符串中找到字典序小的，让它作为起点即可。但是同时我们得保证该字符串的终点不为d，或者以d为结尾的个数不为１，要加上这个判断

现在我们就知道了起点start，我们就从这里出发，开始搜索。

搜索的注意事项：

1.我们需要定义一个flag标记是否已经找到答案。由于是按字典序搜索，第一个找到的答案一定是最优答案。这时候要立即return,在之后的回溯过程中，如果flag==1，也要立即回溯，不然有可能是正确答案被更换掉。（我就是这么错的）

2.记录最终答案和在搜索过程中需要定义两个字符串数组。一个负责在搜索过程中不断更新，另一个负责找到答案后转移。（这样比较保险）

3.当然还需要一个book[]数组，用来判断当前的字符串是否已经用过。搜索前标记成book[]=1;回溯时要记得book[]标记回0；

4.一开始的起点一定要先标记book[]=1;

然后搜索部分就自然地解决啦，我们维护上一个字符串是谁， 在枚举当前字符串的时候，如果该字符串的首字符等于上一个字符串的尾字符，就可以继续往下搜。

AC代码如下：

#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=1e5+5;
string a[maxn];
string ans[maxn];
string now[maxn];
int sum=0;
int len[maxn];
int book[maxn];
map<char,int> s1,s2;
int n;
int flag=0;
void dfs(int last,int step)
{
    if(flag==1)
    return;
    if(step==n)
    {
        flag=1;
        for(int i=1;i<=sum;i++)
        {
            ans[i]=now[i];
        }
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(book[i]==1)
        continue;
        if(a[last][a[last].length()-1]==a[i][0])
        {
            now[++sum]=a[i];
            book[i]=1;
            dfs(i,step+1);
            sum--;
            book[i]=0;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        len[i]=a[i].length();
        s1[a[i][0]]++;
        s2[a[i][len[i]-1]]++;
    }   
    int start=1;
    sort(a+1,a+1+n);
    char s,t;
    for(char c='a';c<='z';c++)
    {
        if(abs(s1[c]-s2[c])==1)
        {
            if(s1[c]-s2[c]==1)
            s=c;
            else
            if(s2[c]-s1[c]==1)
            t=c;
        }
    }
    int cnt=s2[t];
    for(int i=1;i<=n;i++)
    {
        if(a[i][0]==s && (a[i][len[i]-1]!=t || cnt!=1))
        {
            start=i;
            break;
        }
    }
    book[start]=1;
    now[++sum]=a[start];
    dfs(start,1);
    if(flag==0)
    {
        printf("***\n");
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(i!=n)
        cout<<ans[i]<<".";
        else
        cout<<ans[i];
    }
    printf("\n");
    return 0;
}