【算法】单词接龙_单词接龙算法

最近参加校招，看算法。因为DFS考的很多，自己掌握也不是很牢固，就找了一些题。

其中这一道DFS——【单词接龙】，很典型。

大概如下：

    单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现一次两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

   输入的第一行为一个单独的整数n(n<=20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

   只需输出以此字母开头的最长的“龙”的长度

5

at

touch

cheat

choose

tact

a

 

20    

代码如下：看注释就行

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
 
public class Main {
	int n;
	List<String> list;
	String st;
	boolean[] visited;
	int[][] edge;
	int curSum=0;
	String longest = "";
	public Main(){
		n=8;
		list = new LinkedList<String>();
		list.add("at");
		list.add("touch");
		list.add("cheat");
		list.add("choose");
		list.add("tact");
		list.add("about");
		list.add("eclipse");
		list.add("heightandweight");
		st = "a";
		visited=new boolean[n];
		edge = new int[n][n];
		//构造图
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				boolean hasEdge = false;
				//不能和自己相连，且不能存在包含关系
				if(i!=j&&!(list.get(i).contains(list.get(j))||list.get(j).contains(list.get(i)))){	
					int index=0;
					//寻找最长后缀
					while(!hasEdge&&index < list.get(i).length() ){   
						if(list.get(j).startsWith(list.get(i).substring(index, list.get(i).length()))){
							hasEdge = true;							
							edge[i][j] = list.get(i).length()-index;
							break;
						}
						index++;
					}
				}
				System.out.print(edge[i][j]+" ");
			}
			System.out.println();
		}		
		
	}
 
 
	public void getSum(){
		for(int i=0;i<list.size();i++){					
			if(list.get(i).startsWith(st)){
				int sum=list.get(i).length();
				visited[i]=true;
				dfs(i,sum,visited,list.get(i));
				visited[i]=false;
			}
		}
		System.out.println("the answer is:"+curSum);
		System.out.println("the longest dragon is:"+longest);
	}
		
		//递归入口
		public boolean dfs(int i,int a,boolean[] visited,String curString){
			int sum =a;
			String s = new String(curString);
			System.out.println("before:"+s);
			for(int j=0;j<n;j++){			
				if(edge[i][j]>0){
					if(!visited[j]){
						sum+=list.get(j).length();
						sum-=edge[i][j];
						s+=list.get(j).substring(edge[i][j],list.get(j).length());
						System.out.println("after:"+s);
						visited[j]=true;					
						if(dfs(j,sum,visited,s)){    //判断为真,表示已经出现一个解,同时当前节点没有与之相邻的下一个节点了，因此要回溯到上一层
							if(sum>curSum){         //计算当前单词长度，保留最长								
								curSum=sum;
								longest = s;
								System.out.println("sum:"+curSum+" "+"final:"+s);
							}	
							s = s.substring(0, s.length()-list.get(j).length()+edge[i][j]);
							System.out.println("recurse:"+s);
							visited[j]=false;
						}	
						sum-=list.get(j).length();
						sum+=edge[i][j];
					}				
				}
				
			}
			return true;   //遍历完节点了
		}
		
 
 
    public static void main(String[] args){
    	new Main().getSum();
    	
    }
}

控制台输出：

0 1 0 0 1 0 0 0 
0 0 2 2 0 0 0 1 
0 1 0 0 1 0 0 0 
0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 
0 1 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 
0 1 0 0 1 0 0 0 
before:at
after:atouch
before:atouch
after:atoucheat
before:atoucheat
after:atoucheatact
before:atoucheatact
sum:12 final:atoucheatact
recurse:atoucheat
recurse:atouch
after:atouchoose
before:atouchoose
after:atouchooseclipse
before:atouchooseclipse
sum:16 final:atouchooseclipse
recurse:atouchoose
recurse:atouch
after:atoucheightandweight
before:atoucheightandweight
after:atoucheightandweightact
before:atoucheightandweightact
sum:23 final:atoucheightandweightact
recurse:atoucheightandweight
recurse:atouch
recurse:at
after:atact
before:atact
after:atactouch
before:atactouch
after:atactoucheat
before:atactoucheat
recurse:atactouch
after:atactouchoose
before:atactouchoose
after:atactouchooseclipse
before:atactouchooseclipse
recurse:atactouchoose
recurse:atactouch
after:atactoucheightandweight
before:atactoucheightandweight
recurse:atactouch
recurse:atact
recurse:at
before:about
after:aboutouch
before:aboutouch
after:aboutoucheat
before:aboutoucheat
after:aboutoucheatact
before:aboutoucheatact
recurse:aboutoucheat
recurse:aboutouch
after:aboutouchoose
before:aboutouchoose
after:aboutouchooseclipse
before:aboutouchooseclipse
recurse:aboutouchoose
recurse:aboutouch
after:aboutoucheightandweight
before:aboutoucheightandweight
after:aboutoucheightandweightact
before:aboutoucheightandweightact
sum:26 final:aboutoucheightandweightact
recurse:aboutoucheightandweight
recurse:aboutouch
recurse:about
after:aboutact
before:aboutact
after:aboutactouch
before:aboutactouch
after:aboutactoucheat
before:aboutactoucheat
recurse:aboutactouch
after:aboutactouchoose
before:aboutactouchoose
after:aboutactouchooseclipse
before:aboutactouchooseclipse
recurse:aboutactouchoose
recurse:aboutactouch
after:aboutactoucheightandweight
before:aboutactoucheightandweight
recurse:aboutactouch
recurse:aboutact
recurse:about
the answer is:26
the longest dragon is:aboutoucheightandweightact