字符串的排列与组合【Java 递归实现】

清疚 2022-02-20 10:55 308阅读 0赞

我们在笔试中经常会遇到需要对字符串进行排列或者组合的题目。本篇文章对字符串的排列和组合进行递归版本的实现。如果你有更简单易懂的方法，一定要在评论区留下来~

## 1、字符串的组合【子序列】 ##

>  题目：输入一个字符串，输出该字符串中字符的所有组合。
> 
> 例子：输入：abc，它的组合有：a、b、c、ab、ac、bc、abc

*  分析：我们可以将字符串中的每个字符看成二叉树的一个节点，根节点为空，每个节点都会有两种选择：**要** 和 **不要** 两种选择 。那么我们就可以利用递归实现。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

public class 字符串子序列 {
    
        public static void printAllSubString(String str){
            if(str == null){
                return;
            }
    
            char[] chars = str.toCharArray();
            if(chars.length > 0){
                String pre = new String("");   // pre：用于表示从0到i-1位置上形成的结果
                printAllSubString(0, pre, chars);
            }else{
                System.out.println("");     // 输入空字符串也会打印空
            }
        }
    
        public static void printAllSubString(int i, String pre, char[] chars){
            // 迭代终止条件
            if(i == chars.length){
                // 说明已经到最后一个字符了，所有的选择都已经做完了，应该返回了
                System.out.println(pre);
                return;
            }
    
            // 如果没有到最后一个字符，那么当前字符有两种选择：选择要 和 选择不要
            printAllSubString(i + 1, pre, chars);  // 不要当前字符
            printAllSubString(i + 1, pre + String.valueOf(chars[i]), chars);   // 要当前字符
        }
    
        // 测试
        public static void main(String[] args) {
            printAllSubString("abc");
        }
    }

--------------------

## 2、字符串的排列 ##

### 2.1 全排列 ###

> 题目：输入一个字符串，打印出该字符串中字符的所有排列。
> 
> 举例：输入字符串 abc，则输出由字符 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。

*  分析：排列和上面的组合问题思想是一样的：上面的组合问题，每个节点只有 “要” 和 “不要” 两种选择，而排列这里每个节点 i 有  n - i 种选择。
 *  排列问题：所有的排列都是包含该字符串中所有的字符，所以不需要像组合那样利用额外的空间 pre 记录选择的过程。
 *  需要注意的是：i 位置在进行选择的时候，会先和 i + 1 位置交换位置，搞定 i + 1 后面的排列后，会再和 i + 2 ~ n - 1 位置上的每个元素交换一次，所以为了保证都是和 i 位置上的元素进行交换，每次递归一次后，必须要将 i 位置元素再换回原来的位置。
 *  可以直观的理解下：加入现在搞定 i 位置上元素，i  一共有 n - i 种选择，每次 i 位置固定后，i + 1 ~ n - 1 位置上的元素都是同样递归实现。

public class 字符串排列 {
    
        public static void printAllSort(String string){
            if(string == null){
                return;
            }
    
            char[] chars = string.toCharArray();
            if(chars.length > 0){
                printAllSort(0, chars);
            }
        }
    
        // 对i及i以后的字符进行全排列
        public static void printAllSort(int i, char[] chars){
            // 递归终止条件
            if(i == chars.length){
                System.out.println(String.valueOf(chars));
            }
    
            for(int j = i; j < chars.length; j++){
                swap(i, j, chars);   // 第 i 个位置有 i ~ (n - 1) 种选择。n 为字符串的长度
                printAllSort(i + 1, chars);
                swap(i, j, chars);   // 保证 i 后面的字符每次都是和 i 位置上的元素进行的交换，还需要将 i 和 j 交换回来
            }
        }
    
        public static void swap(int i, int j, char[] chars){
            int temp = chars[i];
            chars[i] = chars[j];
            chars[j] = chars[i];
        }
    
        public static void main(String[] args) {
            printAllSort("abcc");
        }
    }

*  运行结果：从运行结果可以看出来，很多排列的结果是重复的，这是全排列的效果。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

### 2.2 去重排列 ###

只需要增加一个 hashset，用于保证重复字符不会被再次交换。

public class 字符串排列_去重 {
    
        public static void printAllSort(String string){
            if(string == null){
                return;
            }
    
            char[] chars = string.toCharArray();
            if(chars.length > 0){
                printAllSort(0, chars);
            }
        }
    
        // 对i及i以后的字符进行全排列
        public static void printAllSort(int i, char[] chars){
            // 递归终止条件
            if(i == chars.length){
                System.out.println(String.valueOf(chars));
            }
    
            // 用于保证每次交换的字符不存在重复的字符
            HashSet<Character> set = new HashSet<>();
            for(int j = i; j < chars.length; j++){
                if(!set.contains(chars[j])){
                    set.add(chars[j]);
                    swap(i, j, chars);   // 第 i 个位置有 i ~ (n - 1) 种选择。n 为字符串的长度
                    printAllSort(i + 1, chars);
                    swap(i, j, chars);   // 保证 i 后面的字符每次都是和 i 位置上的元素进行的交换，还需要将 i 和 j 交换回来
                }
            }
        }
    
        public static void swap(int i, int j, char[] chars){
            int temp = chars[i];
            chars[i] = chars[j];
            chars[j] = chars[i];
        }
    
        public static void main(String[] args) {
            printAllSort("abcc");
        }
    }

*  运行结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220220/0bcdfb80956f4077aa296ca7e3033806.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220220/89b82874eb9844129f043689463f1daf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2]: /images/20220220/1eb0d8ae261146ea825197e8569aa01b.png