leetcode面试题0808有重复字符串的排列组合

左手的ㄟ右手 2024-03-02 03:01 44阅读 0赞

### 描述 ###

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

![84c7d7c75c46759c987fdfc8fcf01e9e.png][]

数据范围：n<10  
要求：空间复杂度 O(n!)，时间复杂度 O(n!)

#### 输入描述： ####

输入一个字符串,长度不超过10,字符只包括大小写字母。

### 示例1 ###

> 输入："ab"
> 
> 返回值：\["ab","ba"\]
> 
> 说明：返回\["ba","ab"\]也是正确的

### 示例2 ###

> 输入："aab"
> 
> 返回值：\["aab","aba","baa"\]

### 示例3 ###

> 输入："abc"
> 
> 返回值：\["abc","acb","bac","bca","cab","cba"\]

### 示例4 ###

> 输入：""
> 
> 返回值：\[""\]

### 思路 ###

这道题就是一个组合，但是要排除重复项。如果直接使用循环，好像并不好下手。

如果我们使用递归的思想，把字符串abc看作a和\[bc\]的组合。我们不用关心\[bc\]组合到底是什么样子，我们最终得到以a开头的组合就是a+\[bc\]。以b开头的组合b+\[ac\],以c开头的组合c+\[ab\]。

在计算以a开头的组合中，我们还需要判断如果\[bc\]中有以a开头的字符。比如aab这种用例的情况，a+\[ab\]，后面进行遍历的时候，我们就不再统计a，直接统计b+\[aa\]。所以最终结果就是aab aba,baa。

大致思路其实已经出来了，伪代码如下：

permutation(abc) {
       list = [];
       set = [];
       for(a,b,c):
         if(!set.contains(a)){
           sublist = permutation(bc)
           for(String str: sublist):
              list.add(a+str)
           set.add(a);
         }
      return list;
    }

在上面aab的例子中，我们开始遍历a的时候，我们需要知道\[ab\]有多少种组合，这样，结果就是a + list(\[ab\]) ，继续拆分ab，这时候就是a+list(\[b\])。当只有一个字母的时候，组合就是一种情况，递归终止。当进行下一次遍历的时候，发现如果是a，那么不用遍历，因为a已经计算过。最后遍历到b，这时候就是b+list(\[aa\])，继续拆分aa，同样是一种情况，最终遍历结束，返回所有的情况。

同理，abc的时候，我们遍历a，我们需要知道剩下的\[bc\]的组合情况，继续拆分b+\[c\]。拆到只剩一个字母的时候，递归结束。接着遍历b、c。为了求出剩下的字符有多少种组合，我们继续拆分，也就是递归，直到剩下一个字母，这时候就是一种情况，递归结束。

### 代码 ###

import java.util.*;
    
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNext()) {
                System.out.println(Permutation(scanner.next()));
            }
            scanner.close();
        }
    
        public static ArrayList<String> Permutation(String str) {
            ArrayList<String> list = new ArrayList<>();
            if (str.length() == 1) {
                list.add(str);
            } else {
                Set<String> set = new HashSet<>();
                for (int i = 0; i < str.length(); i++) {
                    String left = str.substring(i, i + 1);
                    if (!set.contains(left)) {
                        String substr = str.substring(0, i) + str.substring(i + 1);
                        List<String> subList = Permutation(substr);
                        for (int j = 0; j < subList.size(); j++) {
                            list.add(left + subList.get(j));
                        }
                        set.add(left);
                    }
                }
            }
            return list;
        }
    }

运行测试用例：

![1f0ab34430af4116942ef718997758ee.png][]

这道题采用了递归的思想，把字符串拆分为首字母和剩下的子串，这种组合就是首字母和子串列表的组合。 为了求得子串有多少种组合，继续拆分，直到拆分到剩下一个字符串，这时候就是一种情况，拆分结束。当然，字符串有可能会有字母重复，我们在遍历的时候，记录是否已经遍历过当前首字母。

还有一种比较孬的办法，这里不用考虑重复，把所有可能的情况都添加进来，最后把结果放到Set集合中，让它自己去重，虽然也能得到结果，但是时间复杂度不一定能满足算法要求。

而本例的方法是通过了算法测试要求的：

![49250f5f1ee54e05b5b083924b4b75eb.png][]

这种使用递归的办法，我们不需要知道每一种组合到底有多少种，我们只需要根据我们的思路去把字符串拆分成更小的单元，到了一个字母组成的字符串的时候，我们就很明确地知道这种组合情况，递归结束。

最后附上牛客网该题的地址：[https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7][https_www.nowcoder.com_practice_fe6b651b66ae47d7acce78ffdd9a96c7]

[84c7d7c75c46759c987fdfc8fcf01e9e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/321bdb541bde44209ef2d4c0adf01aec.png
[1f0ab34430af4116942ef718997758ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/62b3aab5c34f4a689b5cf180114cc051.png
[49250f5f1ee54e05b5b083924b4b75eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/1b535afd5a164a0f912dc7156a9014f9.png
[https_www.nowcoder.com_practice_fe6b651b66ae47d7acce78ffdd9a96c7]: https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7