暴搜

//长度必须大于等于1，且严格小于两个串的长度

import java.util.*;
class Main{
    static int N = 21, max = 0;
    static Map<String, Integer> map = new HashMap(N);
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = Integer.valueOf(sc.nextLine());
        for(int i = 0; i < n; i++){
            String s = sc.nextLine();
            map.put(s, map.getOrDefault(s, 0) + 2);
        }
        String begin = sc.nextLine();
        for(String s: map.keySet()){
            if(s.charAt(0) == begin.charAt(0)){
                map.put(s, 1);
                dfs(s);
                map.put(s, 2);
            }

        }
        System.out.println(max);
    }

    public static void dfs(String s){
        max = Math.max(s.length(), max);
        int sLen = s.length();
        for(String key: map.keySet()){
            if(map.get(key) == 0) continue;
            int len = Math.min(sLen, key.length()) - 1;
            for(int i = 1; i <= len; i++){
                String left = s.substring(sLen - i, sLen);
                String right = key.substring(0, i);
                if(same(left, right)){
                    String nS = s.substring(0, sLen - i) + key;
                    map.put(key, map.get(key) - 1);
                    dfs(nS);
                    map.put(key, map.get(key) + 1);
                }
            }
        }
    }

    public static boolean same(String a, String b){
        for(int i = 0; i < a.length(); i++){
            if(a.charAt(i) != b.charAt(i)) return false;
        }
        return true;
    }
}

加入性质优化
本题性质：
如果两个单词能相连接， 那么就连接他们最短的共同子串， 这样能获取最长的字符串。
这样一来就可以使用一个二维数组来存储各个字符串之间的最短公共连接串长度了。

import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 21, max = 0, n;
    static int[][] minLen = new int[N][N];
    static int[] st = new int[N];
    static String[] strings = new String[N];
    public static void main(String[] args) throws Exception{
        n = Integer.valueOf(read.readLine());
        Arrays.fill(st, 2);
        for(int i = 0; i < n; i++){
            strings[i] = read.readLine();
        }
        char first = read.readLine().charAt(0);
        //初始化最短两个字符串间的最短连接长度
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                for(int len = 1; len <= 
                  Math.min(strings[i].length(), strings[j].length()) - 1; len ++){
                    if(same(strings[i].substring(strings[i].length() - len), 
                    strings[j].substring(0, len))){
                        minLen[i][j] = len;
                        break;
                    }
                }
            }
        }

        for(int i = 0; i < n; i++){
            if(first == strings[i].charAt(0)){
                st[i]--;
                dfs(strings[i], i);
                st[i]++;
            }
        }
        System.out.println(max);

    }

    public static void dfs(String s, int cur){
        max = Math.max(max, s.length());
        for(int j = 0; j < n; j++){
            if(st[j] == 0 || minLen[cur][j] == 0) continue;
            st[j]--;
            dfs(s + strings[j].substring(minLen[cur][j]), j);
            st[j]++;
        }
    }

    public static boolean same(String a, String b){
        for(int i = 0; i < a.length(); i++) if(a.charAt(i) != b.charAt(i)) return false;
        return true;
    }
}