算法-回溯法-有重复字符串的排列组合

川长思鸟来 2022-10-25 00:59 17阅读 0赞

# 算法-回溯法-有重复字符串的排列组合 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/permutation-ii-lcci/

## 1.2 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]

# 2.1 回溯法 #

## 2.1 解题思路 ##

使用回溯法，每次从首字符开始往后遍历最后所有字符，并用一个boolean数组记录这一趟DFS已经使用过的字符位置，如果已经用过就不再使用，否则添加到StringBuilder末尾。

当StringBuilder长度等于原始字符串长度时，达到结束条件，加入结果集，结果集用HashSet去重。

## 2.2 代码 ##

class Solution { 
    class Solution { 
            Set<String> result = new HashSet<>();
        boolean[] used;
        public String[] permutation(String S) { 
            if(S.length() == 1){ 
                result.add(S);
                return result.toArray(new String[0]);
            }
            used = new boolean[S.length()];
            backtrack(S, new StringBuilder());
            String[] returnR = new String[result.size()];
            int i = 0;
            for(String str : result){ 
                returnR[i++] = str;
            }
            return returnR;
        }
    
        private void backtrack(String S, StringBuilder sb){ 
            if(sb.length() == S.length()){ 
                // 结束条件
                result.add(sb.toString());
                return;
            }
            for(int i = 0; i < S.length(); i++){ 
                if(used[i] == true){ 
                    continue;
                }
                sb.append(S.charAt(i));
                used[i] = true;;
                backtrack(S, sb);
                sb = sb.deleteCharAt(sb.length() - 1);
                used[i] = false;
            }
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20210130133006913.png]

## 2.4 空间复杂度 ##

O(N)

# 3.1 回溯法+交换字符串 #

## 3.1 解题思路 ##

依然使用回溯法，但较于解法2，可用复用固定原始字符串构成的char数组，通过每次交换字符到某固定位置，来完成遍历过程。

结果集用HashSet去重.

## 3.2 代码 ##

class Solution { 
        Set<String> result = new HashSet<>();
        char[] chars;
    
        public String[] permutation(String S) { 
            if(S.length() == 1){ 
                result.add(S);
                return result.toArray(new String[0]);
            }
            chars = S.toCharArray();
            backtrack(0);
            return result.toArray(new String[0]);
        }
    
        private void backtrack(int index){ 
            if(index == chars.length){ 
                // 结束条件
                result.add(new String(chars));
                return;
            }
            for(int i = index; i < chars.length; i++){ 
                swap(index, i);
                backtrack(index + 1);
                swap(index, i);
            }
        }
        private void swap(int i, int j){ 
            char tmp = chars[i];
            chars[i] = chars[j];
            chars[j] = tmp;
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][20210130134540680.png]

## 3.4 空间复杂度 ##

O(N)

# 4.1 回溯法+交换字符串+剪枝 #

## 4.1 解题思路 ##

我们对结果集使用HashSet去重，其实可以在每次遍历时记录该for循环已经使用过的字符，如果发现当前遍历字符已经遍历使用过，则跳过。这样就不需要使用HashSet去重了。

## 4.2 代码 ##

class Solution { 
        List<String> result = new ArrayList<>();
        char[] chars;
    
        public String[] permutation(String S) { 
            if(S.length() == 1){ 
                result.add(S);
                return result.toArray(new String[0]);
            }
            chars = S.toCharArray();
            backtrack(0);
            return result.toArray(new String[0]);
        }
    
        private void backtrack(int index){ 
            if(index == chars.length){ 
                // 结束条件
                result.add(new String(chars));
                return;
            }
            boolean[] used = new boolean[52];
            for(int i = index; i < chars.length; i++){ 
                int trueIndex = chars[i] < 'a' ? chars[i] - 'A' + 26 : chars[i] - 'a';
                if(used[trueIndex] == true){ 
                    continue;
                }
                used[trueIndex] = true;
                swap(index, i);
                backtrack(index + 1);
                swap(index, i);
            }
        }
        private void swap(int i, int j){ 
            char tmp = chars[i];
            chars[i] = chars[j];
            chars[j] = tmp;
        }
    }

## 4.3 时间复杂度 ##

![在这里插入图片描述][2021013014035895.png]

## 4.4 空间复杂度 ##

O(N)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: /images/20221024/c0af7bfe3a9e44bc8838238babf87ae0.png
[20210130133006913.png]: /images/20221024/de8f69cb91e24fa3be352c9d556c80bd.png
[20210130134540680.png]: /images/20221024/1652950356804dc3a382c1c9f9e2f0c0.png
[2021013014035895.png]: /images/20221024/237576a03ff0494c8788270b9ed10286.png