dfs之字符串拼接

P1101 单词方阵 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

总思路，首先按照首字符来在字符串数组中寻找以首字符开头的n个字符串，每一个走一编，最后从所有得到答案中选取最好的。

代码加注释

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.math.MathContext;
import java.security.PublicKey;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;
public class Main {	
  public static void main(String[] args) throws NumberFormatException, IOException  {
Scanner sc=new Scanner(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] aStrings=br.readLine().split(" ");
aa=Integer.parseInt(aStrings[0]);
aaStrings=new String[aa];
bb=new int[aa];
int a;
for(a=0;a
	aaStrings[a]=br.readLine();
}
 
String bString=br.readLine();
char b=bString.charAt(0);
for(a=0;a
	if(aaStrings[a].charAt(0)==b) {//找到首字母符合的字符串
		bb[a]++;//次数使用加一
		answer=aaStrings[a].length();
		dfs(a);
		bb[a]--;
		max=Math.max(max, zhongji);
	}
	
}
System.out.println(zhongji);
	}
  public static int max=0;
  public static int[] bb;
  public static int answer=0;
  public static int aa;
  public static int zhongji=0;
  public static String[] aaStrings;
public static void dfs(int a) {
	int b;
	for(b=0;b
		if(bb[b]<2&&find(a, b)!=0) {//次数不得超过2次同时又能与下一个字符串拼接才可以
			bb[b]++;
			int e=find(a, b);
			answer=answer+e;
			dfs(b);//以下个字符串接着寻找
			answer=answer-e;//回溯
			bb[b]--;
		}
	}
	zhongji=Math.max(zhongji, answer);
  }
public static int find(int a,int b) {//这里是来寻找两个字符串的重合部分，如果不重合，会返回0，否则会返回去除重合部分之后的数
	int alength=aaStrings[a].length();
	int blength=aaStrings[b].length();
	int c;
	for(c=alength-1;c>=1;c--) {//为社么大于等于1，因为从等于一的话可能就是包含关系，不合法
		if(aaStrings[a].charAt(c)==aaStrings[b].charAt(0)) {
			int k=0;//为了尽量取得最大的，我们在第一次有数相等时就开始寻找重合部分
			for(int j=c+1;j<=alength-1;j++) {
				k++;
				if(aaStrings[a].charAt(j)!=aaStrings[b].charAt(k)) {
					return 0;
				}
				
			}
			return blength-(k+1);
		}
	}
	return 0;
}
}