java-37.有n 个长为m+1 的字符串，如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配，则两个字符串可以联接
public class MaxCatenate { /* * Q.37 有n 个长为m+1 的字符串，如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配，则两个字符串可以联接， * 问这n 个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。 */ public static void main(String[] args){ String[] text = new String[]{ "abcd", "bcde", "cdea", "deab", "eaba", "abab", //"babc", "deac", "cdei", "bcdf", "cdfi", "dfic", "cdfk", "bcdg", }; new MaxCatenate().maxCatenate(text); } public void maxCatenate(String[] text){ int size=text.length; int[][] adjMatrix=new int[size][size]; //create Graph.Use adjacent matrix for(int i=0;i<size;i++){ for(int j=0;j<size;j++){ if(this.hasEdge(text[i],text[j])){ adjMatrix[i][j]=1; } } } //create a new array to keep the 'adjMatrix'unchanged. int[][] finalCost=new int[size][size]; for(int i=0;i<size;i++){for(int j=0;j<size;j++){finalCost[i][j]=adjMatrix[i][j];}} int max=0; for(int k=0;k<size;k++){ for(int i=0;i<size;i++){ for(int j=0;j<size;j++){ if(finalCost[i][k]!=0&&finalCost[k][j]!=0&& finalCost[i][k]+finalCost[k][j]>finalCost[i][j]){ finalCost[i][j]=finalCost[i][k]+finalCost[k][j]; max=(max>finalCost[i][j]?max:finalCost[i][j]); } } } } for(int i=0;i<size;i++){ if(finalCost[i][i]>1){//not '>0',consider "bbbb" System.out.println("circle detected"); return; } } System.out.println("maxLength is "+(max+1)); } //true if strA's last m characters equals to strB's first m characters public boolean hasEdge(String strA,String strB){ boolean result=false; String suffix=strA.substring(1); result=strB.startsWith(suffix); return result; }}