[每日一道小算法（五十六）] [字符串] 字符串的全排列

痛定思痛。 2023-07-07 08:07 3阅读 0赞

前言：  
接下来准备做字符串的题型，字符串的题型真的是经常出现，一定得好好学习。

### 题目描述 ###

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。  
输入描述:  
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

### 题目解析 ###

这种题型，其实就是经典的DFS题目。我们做这种题的思想就是，我们先确定一个字符a，然后我们开始对a+1~N-1字符递归使用全排列。  
借用一个图来说明一下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]

### 代码样例 ###

package com.asong.leetcode.Permutation;
    
    import java.util.ArrayList;
    import java.util.Collections;
    
    /** * 字符串全排列 字典 */
    public class Solution { 
        public ArrayList<String> Permutation(String str)
        { 
            ArrayList<String> res = new ArrayList<String>();
            if(str == null || str.length()==0)
            { 
                return res;
            }
            char[] chars = str.toCharArray();
            findPermutation(res,chars,0);
            Collections.sort(res);
            return res;
        }
        //对chars[i~length-1]范围内的字符数组完成全排列,并将结果存入res中
        private  void findPermutation(ArrayList<String> res,char[] chars, int i)
        { 
            if( i == chars.length)
            { 
                String str = new String(chars);
                if(!res.contains(str)) { 
                    res.add(str);
                }
                return;
            }
            //从[i~length-1]枚举确定i位置的字符
            for (int j = i; j < chars.length; j++) { 
                swap(chars,i,j);
                //确定好i的位置,对[i+1~length-1]范围内的字符数组完成全排列
                findPermutation(res,chars,i+1);
                //恢复原数组
                swap(chars,i,j);
            }
        }
        private  void swap(char[] chars,int i,int j)
        { 
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
        }
    
        public static void main(String[] args) { 
           // ArrayList<String> list = Permutation("abc");
           // System.out.println(list);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200221175747238.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1,size_16,color_FFFFFF,t_70