剑指offer27 字符串的排列

剑指offer

27 字符串的排列

---

题目描述

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

输入描述

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路(分治、递归)

固定第一个字符，递归取得首位后面的各种字符串组合；再将第一个字符与后面每一个字符交换，同样递归获得其字符串组合；每次递归都是到最后一位时结束，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。

代码

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        if(str.length()==0 ||str == null){
            return result;
        }
        PermutationHelper(str.toCharArray(),0,result);
        Collections.sort(result);//按字典序输出
        return result;
    }
    private void PermutationHelper(char[] chars,int i,ArrayList<String> result){
        //已经递归到了字符串最后一位，判断集合中有没有这个字符串，没有则加入
        if(i== chars.length-1){
            if(!result.contains(new String(chars))){
                result.add(new String(chars));
                return;
            }
        }else{
            //首次传进来的i为0，代表首位字符
            //依次处理i与i后面的每个字符(索引j)交换
            for(int j=i; j<chars.length; j++){
                swap(chars,i,j);//交换
                PermutationHelper(chars,i+1,result);//继续递归交换后的子串
                swap(chars,i,j);//还原。每次交换排列完成之后一定要将原来的字符换回来，确保字符顺序正确
            }
        }
    }
    private void swap(char[] chars,int i,int j){
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}

reference

https://blog.csdn.net/qq_42039996/article/details/84504574