【剑指offer】面试题38：字符串的排列

╰半夏微凉° 2022-03-26 21:06 179阅读 0赞

> 博主秋招提前批已拿百度、字节跳动、拼多多、顺丰等公司的offer，可加微信：**pcwl\_Java** 一起交流秋招面试经验，可获得博主的秋招简历和复习笔记。

> **题目：输入一个字符串，按字典序打印出该字符串中字符的所有排列。**

牛客网链接： [https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7][https_www.nowcoder.com_questionTerminal_fe6b651b66ae47d7acce78ffdd9a96c7]

例如输入字符串abc,则打印出由字符 a、b、c 所能排列出来的所有字符串abc、acb、bac、bca、cab 和 cba。

我们求整个字符串的排列，可以看成两步：

第一步：求出所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。

第二步：固定第一个字符，求后面所有字符的排列。这个时候我们仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

将上诉过程，翻译成代码如下：

感觉这道题目从思想上不难理解，但是代码实现还是有难度的，在牛客网上看到了一个注释比较清楚的答案，Mark在这里。

需要两个swap的原因是：当一个字符串到最后两个字母的排序时，都会有两种：AB 和 BA，一次交换其实交换的是自身，另外一次是交换两个字符。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

import java.util.ArrayList;
    import java.util.List;
    import java.util.Collections;
    public class Solution {
        public ArrayList<String> Permutation(String str) {
            List<String> resultList = new ArrayList<>();
            if(str.length() == 0)
                return (ArrayList)resultList;
            //递归的初始值为（str数组，空的list，初始下标0）
            fun(str.toCharArray(),resultList,0);
            Collections.sort(resultList);
            return (ArrayList)resultList;
        }
         
        private void fun(char[] ch,List<String> list,int i){
            //这是递归的终止条件，就是i下标已经移到char数组的末尾的时候，考虑添加这一组字符串进入结果集中
            if(i == ch.length-1){
                //判断一下是否重复
                if(!list.contains(new String(ch))){
                    list.add(new String(ch));
                    return;
                }
            }else{
                //这一段就是回溯法，这里以"abc"为例
                 
                //递归的思想与栈的入栈和出栈是一样的,某一个状态遇到return结束了之后，会回到被调用的地方继续执行
                 
                //1.第一次进到这里是ch=['a','b','c'],list=[],i=0，我称为 状态A ，即初始状态
                //那么j=0，swap(ch,0,0)，就是['a','b','c']，进入递归，自己调自己，只是i为1，交换(0,0)位置之后的状态我称为 状态B 
                //i不等于2，来到这里，j=1，执行第一个swap(ch,1,1)，这个状态我称为 状态C1 ,再进入fun函数，此时标记为T1，i为2，那么这时就进入上一个if，将"abc"放进list中
                /-------》此时结果集为["abc"]
                 
                //2.执行完list.add之后，遇到return，回退到T1处，接下来执行第二个swap(ch,1,1)，状态C1又恢复为状态B
                //恢复完之后，继续执行for循环，此时j=2,那么swap(ch,1,2),得到"acb"，这个状态我称为C2,然后执行fun，此时标记为T2,发现i+1=2,所以也被添加进结果集，此时return回退到T2处往下执行
                /-------》此时结果集为["abc","acb"]
                //然后执行第二个swap(ch,1,2)，状态C2回归状态B,然后状态B的for循环退出回到状态A
                 
                //             a|b|c(状态A)
                //               |
                //               |swap(0,0)
                //               |
                //             a|b|c(状态B)
                //             /  \
                //   swap(1,1)/    \swap(1,2)  (状态C1和状态C2)
                //           /      \
                //         a|b|c   a|c|b
                 
                //3.回到状态A之后，继续for循环，j=1,即swap(ch,0,1)，即"bac",这个状态可以再次叫做状态A,下面的步骤同上
                /-------》此时结果集为["abc","acb","bac","bca"]
                 
                //             a|b|c(状态A)
                //               |
                //               |swap(0,1)
                //               |
                //             b|a|c(状态B)
                //             /  \
                //   swap(1,1)/    \swap(1,2)  (状态C1和状态C2)
                //           /      \
                //         b|a|c   b|c|a
                 
                //4.再继续for循环，j=2,即swap(ch,0,2)，即"cab",这个状态可以再次叫做状态A，下面的步骤同上
                /-------》此时结果集为["abc","acb","bac","bca","cab","cba"]
                 
                //             a|b|c(状态A)
                //               |
                //               |swap(0,2)
                //               |
                //             c|b|a(状态B)
                //             /  \
                //   swap(1,1)/    \swap(1,2)  (状态C1和状态C2)
                //           /      \
                //         c|b|a   c|a|b
                 
                //5.最后退出for循环，结束。
                 
                for(int j=i;j<ch.length;j++){
                    swap(ch,i,j);
                    fun(ch,list,i+1);
                    swap(ch,i,j);
                }
            }
        }
         
        //交换数组的两个下标的元素
        private void swap(char[] str, int i, int j) {
                if (i != j) {
                    char t = str[i];
                    str[i] = str[j];
                    str[j] = t;
                }
            }
        }

![20190112170737626.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2][]

个人感悟：对于这类用递归代码实现的问题过程，不要尝试去理解它的全过程，比较“递归是神”。你只要找出它的特点，找出问题拆解的方案，大的问题的解决方案也适用于小的，不要去跟着递归想那么多趟。就比如组合这题：对于a、b和c，那么其实就是包括两种情况：包含a的组合，和不包含a的组合。至于后面的继续拆分，就交给递归去做吧。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 4][]

![20190112171819383.png][]

[https_www.nowcoder.com_questionTerminal_fe6b651b66ae47d7acce78ffdd9a96c7]: https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220327/5937c1aefb6c4129a68991b09cba0c83.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220327/3a615051684d44ce9ecc77889314a64a.png
[20190112170737626.png]: /images/20220327/ddf19e7ba89141238ffe33c380e1180b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2]: /images/20220327/d0901aa9c5f748f29dee4de93ea7797d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 3]: /images/20220327/7a5592f32aed44328e8e3bfd70e8846c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 4]: /images/20220327/7bdf4b906a1d4ce298eb99b512c37660.png
[20190112171819383.png]: /images/20220327/dc4392c123a2487991a995178706fa96.png