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

港控/mmm° 2022-10-25 00:51 64阅读 0赞

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

# 1 题目概述 #

## 1.1 题目出处 ##

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

## 1.2 题目描述 ##

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

# 2.1 回溯法 #

## 2.1 解题思路 ##

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

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

## 2.2 代码 ##

class Solution { 
        List<String> result = new ArrayList<>();
        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());
            return result.toArray(new String[0]);
        }
    
        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 时间复杂度 ##

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

## 2.4 空间复杂度 ##

O(N)

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

## 3.1 解题思路 ##

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

## 3.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;
            }
            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 时间复杂度 ##

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

## 3.4 空间复杂度 ##

O(N)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: /images/20221024/f2d2f4a94c9d42c4b4c302d8cda3e24a.png
[2021013011440116.png]: /images/20221024/03e9ee2e9f0f4377a6e796a919bde3f6.png
[20210130132025967.png]: /images/20221024/e201864ccf324dd783f29c080a0fbdd6.png