剑指 Offer 38. 字符串的排列【12】

我会带着你远行 2023-09-27 12:04 105阅读 0赞

> **难度等级：中等**

> **上一篇算法：**
> 
> [剑指 Offer 20. 表示数值的字符串【字符串】][Offer 20.]

> **力扣此题地址：**
> 
> [剑指 Offer 38. 字符串的排列 - 力扣（Leetcode）][Offer 38. _ - _Leetcode]

### 1.题目：字符串的排列 ###

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

### 2.解题思路： ###

> 递归、分两步。1. 先求出所有可能出现在第一个位置的字符，然后用第一个字符和后面所有字符交换。2. 固定第一个字符，让第二个字符和它后面所有的字符交换，以此类推。

### 3.代码实现： ###

import java.util.*;
    public class Solution {
        ArrayList<String> res=new ArrayList<>();
        public ArrayList<String> Permutation(String str) {
           if(str==null||str.length()==0)
               return res;
           Permutation(str.toCharArray(),0);
           Collections.sort(res);
           return res;
        }
        public void Permutation(char[] strArr,int begin){
            if(begin==strArr.length-1){
                String s=String.valueOf(strArr);
                if(!res.contains(s))
                    res.add(s);
            }else{
                for(int i=begin;i<strArr.length;i++){ //依次将后面的与begin交换
                    swap(strArr,begin,i);
                    Permutation(strArr,begin+1);
                    swap(strArr,begin,i);
                }
            }
        }
        public void swap(char[] strArr,int a,int b){
            char temp=strArr[a];
            strArr[a]=strArr[b];
            strArr[b]=temp;
        }
    }

[Offer 20.]: https://blog.csdn.net/m0_51697147/article/details/127331547
[Offer 38. _ - _Leetcode]: https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/description/