剑指offer——字符串的排列

题目:
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

分析:
首先,不考虑重复的情况下
固定第一个字符，递归取得首位后面的各种字符串组合；
再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合;
递归的出口，就是只剩一个字符的时候，
递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
如:abc,固定a,得a+bc;a+cb;a与b交换,b+ac,b+ca;a与c交换c+ba,c+ab,得到六个结果.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Arrays;
import java.util.Collections;

public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> ret = new ArrayList<String>();
        if(str.length()==0)return ret;
        char[] array = str.toCharArray();
        doArrays(ret,array,0);
        Collections.sort(ret);
        return ret;
    }
    public void doArrays(ArrayList<String> ret, char[] array, int state){
        if(state == array.length-1){
            ret.add(String.valueOf(array));
            return;
        }
        for(int j = state;j<array.length;j++){
            swap(array,state,j);
            doArrays(ret,array,state+1);
            swap(array,j,state);
        }
    }
    public void swap(char[]array,int i,int j){
        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

考虑循环时,
如abb,a+bb,a+bb;a与第一个b交换,b+ab,b+ba;a与第二个b交换,b+ab,b+ba.实际结果只有abb,bab,bba三种.
当a固定时,操作的子串是bb,bb交换的结果只有一个;
a与第一个b交换时,得到两个新的解;与第二个b交换的结果与第一个相同;
由此,我们可以判断,如果要交换的字符已经在前面出现过时,就不再交换该字符.那么上面的代码就修改为:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Arrays;
import java.util.Collections;
 
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> ret = new ArrayList<String>();
        if(str.length()==0)return ret;
        char[] array = str.toCharArray();
        doArrays(ret,array,0);
        Collections.sort(ret);
        return ret;
    }
    public void doArrays(ArrayList<String> ret, char[] array, int state){
        if(state == array.length-1){
            ret.add(String.valueOf(array));
            return;
        }

        HashSet<Character> charSet = new HashSet<>();//用来筛选是否出现过相同字符

        for(int j = state;j<array.length;j++){
            if(j==state||!charSet.contains(array[j])){//如果包含该字符,就不进行交换操作了.
            //添加j==state判断是为了遇到类似bbc这样的情况,第一个b固定,不让第二个b和c交换了.导致错误.
                charSet.add(array[j]);//把每个出现的字符都加入筛选
                swap(array,state,j);
                doArrays(ret,array,state+1);
                swap(array,j,state);
            }
        }
    }
    public void swap(char[]array,int i,int j){
        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}