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