百度笔试题，这道题有没有简单思路。

/* 题目：判断给定的字符串组， 将字符串排列后，是否存在一种排列，使字符串能够连成一串。 * 即前一个字符串的最后一个字符，等于后一个字符串的第一个字符。 * 如：["abcd","def","fgh","hij"]满足要求 * ["abcd","def","ggh","hij"]不满足要求 * 思路：典型的全排列问题 * 将字符串进行全排列，对每一种排列判断是否满足要求 * 参考: * 递归解决全排列生成算法 http://blog.csdn.net/xiazdong/article/details/7986015 */ //pass public class WordListOrder { public static int canArrangeWords(String arr[]) { boolean found = perm(arr, 0, arr.length - 1); if (found) { return 1; } else { return - 1; } } public static boolean perm(String arr[], int begin, int end) { if (begin == end) { if (check(arr)) {//判断是否满足要求 return true; } else { return false; } } else { boolean found = false; for (int i = begin; i <= end; i++) { swap(arr, begin, i); found = perm(arr, begin + 1, end); if (found) {//符合要求直接退出 break; } swap(arr, begin, i); } return found; } } public static void swap(String[] arr, int x, int y) { String temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } //判断是否符合要求，即前一个字符串的最后一个字符等于当前字符串的第一个字符 public static boolean check(String[] arr) { for (int i = 1; i < arr.length; i++) { if (arr[i].charAt(0) != arr[i - 1].charAt(arr[i - 1].length() - 1)) { return false; } } return true; } // public static void main(String args[]) { // String[] arr = new String[]{"abcd","defg","ghij","okl"}; // int result = canArrangeWords(arr); // System.out.println(result); // } }

public class WordArrange { public static void swap(int begin,int end,String[]arr){ //交换数组中的两个元素 if(begin==end||arr[begin].equals(arr[end]))return; String temp=arr[begin]; arr[begin]=arr[end]; arr[end]=temp; } public static int getAllOrder(int begin,int end,String[]arr) throws Exception{ //获取全排列 //boolean find=false; if(begin==end){ if(check(arr)==1){ throw new Exception(); /*******！出现后以异常方式跳出递归！*********/ } } else{ for(int i=begin;i<=end;i++){ swap(begin,i,arr); getAllOrder(begin+1,end,arr); swap(i,begin,arr); } } return -1; } public static int check(String[]arr){ //在全排列中检查是否有符合要求的排列 for(int i=0;i<arr.length-1;i++){ if(arr[i].charAt(arr[i].length()-1)!=arr[i+1].charAt(0))return 0; } return 1; } public static int canArrangeWords(int num,String[]arr){ //判断输入条件：输入数组长度是否合适、输入数组中每个字符串长度是否合适、输入字母是否是小写。。。。 if(num<1||num>100||num!=arr.length)return 0; int []len=new int[num]; char []head=new char[num]; char []tail=new char[num]; // String []head_tail=new String[num]; for(int i=0;i<num;i++){ len[i]=arr[i].length(); if(len[i]<2||len[i]>100)return 0; head[i]=arr[i].charAt(0); if(head[i]<'a'||head[i]>'z')return 0; tail[i]=arr[i].charAt(len[i]-1); if(tail[i]<'a'||tail[i]>'z')return 0; //head_tail[i]=Character.toString(head[i])+Character.toString(tail[i]); } //采用全排列思想,并通过异常方式在找到符合条件的排列时跳出递归。 try { return getAllOrder(0,num-1,arr); } catch (Exception e) { // TODO Auto-generated catch block return 1; } } public static void main(String[]args){ int num=5; String[]arr={"aa","cab","bc","cd","de"}; System.out.print(canArrangeWords(num,arr)); } }

图的遍历吧

def wordladder(strings): def wordladderRecu(strings, used, cur, length): if len(cur) == length: return 1 for i in xrange(length): if not cur or (not used[i] and strings[i][0] == cur[-1][len(cur[-1])-1]): used[i] = True cur.append(strings[i]) result = wordladderRecu(strings, used, cur, length) cur.pop(-1) used[i] = False if result: return 1 return 0 length = len(strings) used = [False]*length return wordladderRecu(strings, used, [], length) if __name__=="__main__": print wordladder(["hello","world","open","dog","now"]) print wordladder(["dog","world"]) print wordladder(["hello","world"])

类似 全排列 吧

其实就是一个有向图的欧拉回路问题