[劍指offer] 字元串的排列

本文首發于我的個人部落格： 尾尾部落

題目描述

輸入一個字元串,按字典序列印出該字元串中字元的所有排列。例如輸入字元串abc,則列印出由字元a,b,c所能排列出來的所有字元串abc,acb,bac,bca,cab和cba。

輸入描述:

輸入一個字元串,長度不超過9(可能有字元重複),字元隻包括大小寫字母。

解題思路

剛看題目的時候，可能會覺得這個問題很複雜，不能一下子想出解決方案。那我們就要學會把複雜的問題分解成小問題。我們求整個字元串的排列，其實可以看成兩步：

• 第一步求所有可能出現在第一個位置的字元（即把第一個字元和後面的所有字元交換[相同字元不交換]）；
• 第二步固定第一個字元，求後面所有字元的排列。這時候又可以把後面的所有字元拆成兩部分（第一個字元以及剩下的所有字元），依此類推。這樣，我們就可以用遞歸的方法來解決。

參考代碼

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    ArrayList<String> res = new ArrayList<String>();
    public ArrayList<String> Permutation(String str) {
        if(str == null)
            return res;
        PermutationHelper(str.toCharArray(), 0);
        Collections.sort(res);
        return res;
    }
    public void PermutationHelper(char[] str, int i){
        if(i == str.length - 1){
            res.add(String.valueOf(str));
        }else{
            for(int j = i; j < str.length; j++){
                if(j!=i && str[i] == str[j])
                    continue;
                swap(str, i, j);
                PermutationHelper(str, i+1);
                swap(str, i, j);
            }
        }
    }
    public void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
}