/* 题目：判断给定的字符串组， 将字符串排列后，是否存在一种排列，使字符串能够连成一串。 * 即前一个字符串的最后一个字符，等于后一个字符串的第一个字符。 * 如：["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); // } }