剑指Offer-24——字符串的排列

题目描述

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

输入描述:

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

思路解析

刚开始做这个题，确实是毫无思路。。。。。然后看了别人的解法，全都是一大堆的代码。而这个题被定为了1星难度。。。。害，菜鸡の裂开。
然后就老老实实看看人家怎么做的吧。

• （1）首先，这个题其实就是一个全排列嘛。虽然有重复数据，但怎么说其实也就是重复排列问题。OS:感觉排列组合问题真的是面试笔试中的常客了。面试数学题，笔试编程题。换着方式来虐你。其实要是高中，就这排列组合？不是随便做吗？哦，是大学生啊？那打扰了dog.jpg。所以说，大学还是得好好把数学学号，基础的，厉害的都得要学。数学建模那么复杂的奇怪公式都能搞出来，却在高中数学败了，亏。
• (2) 在将全排列问题转换为代码来解决的时候，经常用到的就是DFS（没错，经常看到面经上面下，用dfs,dfs秒了，自己也曾经懵过）。深度优先搜索算法（Depth First Search，简称DFS）。附上一篇相关博客：DFS(深度优先搜索算法)
  DFS实际上就是回溯的思想。将遍历过的登记，然后在还原，重新进入遍历中。

int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}
 
void dfs(int step)
{
        判断边界
        {
            相应操作
        }
        尝试每一种可能
        {
               满足check条件
               标记
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）
        }
}  

• （3）在这个题目中，我们遍历ABC。（借用来自牛客的图：）
  
  我们可以看到，实际上就是将ABC进行了一个全排，首先将A置于首位，另外的每一个都被排序了，然后一种排序完后，将A变为原状。将另外一个与A交换位置，进行再一次的遍历排序。
• (4) 这里我们首先需要将字符串分割位字符数组。然后进行排列。在排列之前，我们先对其进行一个排序，因为需要以字典序的顺序输出，排序后，首字母就会是字典序需要的第一个字母。
• （5）然后用回溯方法进行解决。这个过程中我们需要设置check条件，当然就是A,B,C这样都遍历了一次，就是一次check条件了，check符合要求的就是一条路径。而在循环的排序过程中，我们可以使用StringBuilder来进行添加，拼装好对应的字符串。至于循环里面的，就是排序操作加上对应遍历状态的回溯了。至于重复的路径，就交给TreeSet解决吧。

• 说了这么多，我觉得还是得懂回溯法才有用，要不然真的啥也不知道。我做的时候也是一脸懵，看着也一脸懵，去读了好几个回溯,DFS的博客才明白的。因此还是直接上代码吧。

import java.util.ArrayList;
import java.util.TreeSet;
import java.util.Arrays;
public class Solution {
 private ArrayList<String> res = new ArrayList<>();
    private TreeSet<String> paths = new TreeSet<>();//用于存储路径，还可以自动去重复
    private StringBuilder path = new StringBuilder();//拼接路径
    private boolean[] visited;//对于遍历状态的标记
    public ArrayList<String> Permutation(String str) {
        if (str == null || str.equals("")) {
            return res;
        }
        char[] strs = str.toCharArray();
        //先排序，以符合字典序输出的要求。
        Arrays.sort(strs);
        //标记
        visited = new boolean[strs.length];
        combination(strs, 0);
        res.addAll(paths);
        return res;
    }

    private void combination(char[] strs, int len) {
    //如果len==数组长度，说明遍历完一次了。
    //如A，B，C路径,初始len为0，移动一次加一，
    //当len移动到末尾，说明已经遍历到了C。是一个路径了，可以返回了。
        if (len == strs.length) {
            paths.add(path.toString());
            return;
        }
        for (int i = 0; i < strs.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                path.append(strs[i]);
                combination(strs, len + 1);
                //回溯,将状态重置。如ABC路径获得了，就将其都变为没有访问过。重新开始
                visited[i] = false;
                path.deleteCharAt(path.length() - 1);
            }
        }
    }
}

本文地址：https://blog.csdn.net/H1517043456/article/details/107363629