今天看到迅雷的一個筆試題，一時手癢，便拿來試試，具體題目是這樣的：
請打印出一個字符串中所有字母的全排列結果，比如輸入字符串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
山風小子 閱讀(3089)
評論(5) 編輯 收藏 所屬分類:
Algorithm