$$\color{Red}{单词接龙【DFS之搜索顺序】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

深度优先遍历

这道题难点不在于搜索，而是先抽象求最短公共前后缀的字符串，这里就利用保存长度的思想，我们从小开始枚举，且这个长度按题目要求不能超过字符串本身长度。故遍历需要限制长度条件。

至于dfs需要进行还原现场，为了每次更新知道是在哪个串的基础上更新的，我们需要dfs多开一个参数存上一次使用的串的下标，然后找能和它拼接的串，进行拼接和dfs。

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int N = 25, n, ans = 0;
    static int[][] g = new int[N][N];
    static char start;
    static String[] words = new String[N];
    static int[] used = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void dfs(String s, int index) {
        ans = Math.max(ans, s.length());
        used[index]++;
        for (int i = 0; i < n; i++) {
            if (g[index][i] != 0 && used[i] < 2)
                dfs(s + words[i].substring(g[index][i]), i);
        }
        used[index]--;
    }

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) words[i] = br.readLine();
        start = br.readLine().charAt(0);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                String a = words[i], b = words[j];
                for (int k = 1; k < Math.min(a.length(), b.length()); k++)
                    if (a.substring(a.length() - k).equals(b.substring(0, k))) {
                        g[i][j] = k;
                        break;
                    }
            }
        }
        for (int i = 0; i < n; i++) {
            if (words[i].charAt(0) == start) dfs(words[i], i);
        }
        System.out.println(ans);
    }
}