AcWing 1117. 单词接龙 Java

import java.util.*;
public class Main {
    static int n;
    static String[] s;//存储输入的字符串
    static int[] use;//还可用使用的次数，最多两次
    static String max="";//最大的结果

    public static void dfs(String ans) {
        for(int i = 0;i < n;i++) {
            int t = same(ans,s[i]);
            // 还可用&&有公共部分
            if(t>0&&use[i]>0) {
                use[i]--;
                dfs(ans+s[i].substring(t));
                use[i]++;//回溯
            }
        }
        if(ans.length()>max.length()) max = ans;
        return;
    }

    // 获取公共部分的长度
    public static int same(String s1,String s2) {
        int n1 = s1.length();int n2 = s2.length();
        for(int i = 1;i < Math.min(n1,n2);i++) {
            String t1 = s1.substring(n1-i);//s1取后面
            String t2 = s2.substring(0,i);//s2取前面
            //System.out.println(t1+":"+t2);
            if(t1.equals(t2)) {
                return i;
            }
        }
        return 0;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = new String[n+10];
        use = new int[n+10];

        for(int i = 0;i < n;i++) {
            s[i] = sc.next();
            use[i] = 2;
        }
        char c = sc.next().charAt(0);
        for(int i = 0;i < n;i++) {
            // 找龙头
        if(c==s[i].charAt(0)) {
            use[i]--;
            dfs(s[i]);
            use[i]++;//回溯
            }
        }
        //System.out.println(max);
        System.out.println(max.length());
    }
}