全排列延伸编程题目

问题描述

拉姆刚刚开始学习英文字母，并已经注意有趣的单词阵列。他想确定他是否能将最足单词排列在一个列表中，使得改列表中任何单词的首字母与其前面单词的尾字母相同。你能编写一个计算机程序来帮助拉姆吗？

类WordListOrder的方法canArrangesWords的输入应包含一个单词数组arr

如果列表中单词可按照要求的方式排列，返回1，否则，返回-1.在这种排列中，第一个单词的首字母和最后一个单词的尾字母可以为任意字母，不需要满足约束条件。

算法思路：对字符串数组进行全排列，得到一个排序时扫描字符数组检查是否符合条件

public class WordListOrder { public static void canArrangeWords(String []arr,int start,int len){ if(start==len-1){ int i=1; for(;i<len;i++){ if(arr[i-1].charAt(arr[i-1].length()-1)!=arr[i].charAt(0)) break; } if(i==len){ for(String str:arr){ System.out.print(str+" "); } System.out.println(); flag=true; } } else{ for(int i=start;i<len;i++){ swap(arr,start,i); canArrangeWords(arr,start+1,len); swap(arr,start,i); } } } public static boolean flag; public static void swap(String[] arr,int i,int j){ String temp=new String(); temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } public static void main(String[] args) { String [] arr={"1","2","3"}; canArrangeWords(arr,0,arr.length); System.out.println(flag); // TODO Auto-generated method stub } }

全排列的递归算法从上面空间扩展的图就可以看出来 - 每层循环针对一个元素，把这个元素和它后面的元素调换一次位置(包含自身)，再展开对下一个元素的循环。展开完之后再调换回来。 -可以观察到每层循环的arrange(str,start,len)都是一样的。

现在看来我是懂了,不知道下次再看我能不能敲出代码，时常巩固基础。 参考博客 全排列算法 相同问题的巧妙C++实现