今天看到迅雷的一个笔试题，一时手痒，便拿来试试，具体题目是这样的：
请打印出一个字符串中所有字母的全排列结果，比如输入字符串abc，则打印出abc, acb, bac, bca, cab, cba
下面是我的解法，由于时间仓促，没有仔细研究，无法保证这是最优的
：
package
edu.ecust.test;
import
java.util.ArrayList;
import
java.util.Iterator;
import
java.util.List;
public
class
Test
{
public
static
void
main(String[] args)
{
System.out.println(range(
"
abc
"
));
}
public
static
List
<
String
>
range(String str)
{
if
(
1
==
str.length())
{
List
<
String
>
result
=
new
ArrayList
<
String
>
();
result.add(str);
return
result;
}
char
[] chars
=
str.toCharArray();
List
<
String
>
result
=
new
ArrayList
<
String
>
();
for
(
int
i
=
0
, n
=
chars.length; i
<
n; i
++
)
{
char
[] swapedChars
=
swapElems(i, chars);
char
c
=
swapedChars[
0
];
char
[] remainChars
=
new
char
[swapedChars.length
-
1
];
System.arraycopy(swapedChars,
1
, remainChars,
0
, swapedChars.length
-
1
);
String remainStr
=
new
String(remainChars);
List
<
String
>
partialResult
=
range(remainStr);
for
(Iterator
<
String
>
it
=
partialResult.iterator(); it.hasNext(); )
{
result.add(c
+
it.next());
}
}
return
result;
}
public
static
char
[] swapElems(
int
index,
char
[] array)
{
char
[] chars
=
new
char
[array.length];
System.arraycopy(array,
0
, chars,
0
, array.length);
char
c
=
chars[index];
for
(
int
i
=
index
-
1
; i
>=
0
; i
--
)
{
chars[i
+
1
]
=
chars[i];
}
chars[
0
]
=
c;
return
chars;
}
}
posted on 2006-11-03 19:07
山风小子 阅读(3084)
评论(5) 编辑 收藏 所属分类:
Algorithm