轉載請注明出處:http://blog.csdn.net/xiaojimanman/article/details/17585499
今天突然之間想起了自己來易查面試時的一個筆試題目,題目大緻如下:求字元串s的全排列。
其實這個題目的實作方式也就是遞歸調用,當時也就寫了一下僞代碼,今天就把完整的實作方式和大家分享下。
下面的實作方式也存在一些小BUG,比如:對于字元串中出現相同的字元是按照不同字元去處理的,當然對于這個BUG可以将程式中的ArrayList<String> 全部修改為 HashSet<String>即可解決,但是自己通過測試,後面的效率明顯比第一個低,在實際中,有時候就需要把它們當成不同的字元去對待,自己就偷懶不處理了;第二個BUG就是由于ArrayList<String>數組最大長度的限制,是以現在最大也就隻能處理9個長度的字元串,修改這個應該就需要考慮另外的資料結構了。
廢話不說了,直接貼出代碼:
/**
*@Description: 字元串排列問題
*/
package cn.lulei.util;
import java.util.ArrayList;
public class StringPermutation {
/**
* @param s
* @return
* @Date: 2013-12-26
* @Author: lulei
* @Description: 求字元串的全排列,在測試中,字元長的長度最大為9
* 字元串全排列的實作思想:字元串 s 的全排列是字元串 s 的子串 (s除去第一位的字元組成的字元串)的全排列結果
* 和字元 c (s第一個位置的字元)經過getStr(String s, char c)運算結果,如果 s 長度為 1 這其全排列結果就是本身
* 例如:"abcde" 的全排列結果是 "bcde" 的全排列結果和 'a' 經過getStr(String s, char c)運算得到響應的結果
* 由于在實作過程中使用 ArrayList 造成可以處理的字元串長度 最大隻能為 9,在實作過程中,未考慮 s 中有重複字元存在情況
*/
public static ArrayList<String> getFullPermutation(String s) {
if (null == s || "".equals(s)){
return null;
}
ArrayList<String> array = null;
if (s.length() == 1){
array = new ArrayList<String>();
array.add(s);
} else {
//遞歸調用
array = getFullPermutation(s.substring(1), s.charAt(0));
}
return array;
}
/**
* @param s
* @param c
* @return
* @Date: 2013-12-26
* @Author: lulei
* @Description: 求字元串 s + c 的全排列結果
*/
public static ArrayList<String> getFullPermutation(String s, char c) {
ArrayList<String> reArray = new ArrayList<String>();
ArrayList<String> array = getFullPermutation(s);
for (String str : array){
reArray.addAll(getStr(str, c));
}
array = null;
return reArray;
}
/**
* @param s
* @param c
* @return
* @Date: 2013-12-26
* @Author: lulei
* @Description: 将字元 c 插入到字元串的每個位置中
* 如: s = "ab"; c = 'c';得到的結果就是 "cab" "acb" "abc"
*/
public static ArrayList<String> getStr(String s, char c) {
ArrayList<String> array = new ArrayList<String>();
for (int i = 0; i <= s.length(); i++) {
array.add(new StringBuffer().append(s.substring(0, i)).append(c).append(s.substring(i)).toString());
}
return array;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//,處理9個字元的全排列耗時 ~ 370ms 全排列結果個數 362880
String s = "abcdefghi";
long a = System.currentTimeMillis();
ArrayList<String> array = StringPermutation.getFullPermutation(s);
long b = System.currentTimeMillis();
System.out.println(s.length() + "個字元串長度全排列耗時:" + (b -a) + "ms");
if (array != null){
System.out.println(array.size());
}
}
}
自己如果解決了字元串長度限制的這個BUG,會在後面給出相應的blog位址。