[算法学习]Java实现字符串全排列

算法

思路：这里用到递归的方式完成字符数据的全排列，递归确实很方便。看似没用到辅助空间，实际上却是消耗了栈空间（“递归栈”），递归用起来也不是那么简单，解决问题用递归的时候，一定要关注到两个零界点，怎么开始和怎么结束。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * 实现字符数组全排列
 * 
 * @author kesar
 * 
 */
public class TestPermute 
{

	public static void permute(String str) 
	{

		char[] ca = str.toCharArray();
		permute(ca, 0, ca.length - 1);
	}

	/**
	 * 核心方法：用了递归的方式完成全排列，用递归的思路是要怎么开始，怎么结束，想想这两个临界点。
	 * @param str
	 * @param low
	 * @param hight
	 */
	public static void permute(char[] str, int low, int hight) 
	{

		if (low == hight) 
		{
			// 递归结束
			for (int i = 0; i <= hight; i++)
				System.out.print(str[i]);
			System.out.println();
		} 
		else 
		{
			for (int i = low; i <= hight; i++) 
			{
				//首先交换开始的字符位置(这里交换字符值不能用异或，会出现奇怪字符)
				//这个交换是思路的关键，因为不想用辅助空间(一用就很多浪费)，所以才选择交换位置。
				char temp = str[low];
				str[low] = str[i];
				str[i] = temp;

				// 递归开始
				permute(str, low + 1, hight);
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) 
	{
		permute("abc");
	}

}

输出

abc
acb
cab
cba
abc
acb