面试题 08.08. 有重复字符串的排列组合--回溯算法回溯算法

LeetCode 面试题 08.08. 有重复字符串的排列组合有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合
示例1：

输入：S = "qqe" 输出：["eqq","qeq","qqe"]

示例2：

输入：S = "ab" 输出：["ab", "ba"]

解法：回溯法解题思路：首先，要求一个字符串的各种组合，我们第一个想法肯定是通过for循环，那么for循环的层数是多少勒，应该是该字符串的长度，然后通过for循环来进行匹配，但是，我们应该要注意一个问题，在进行排列组合的时候，可能会出现重复的字符串，比如说
【面试题 08.08. 有重复字符串的排列组合--回溯算法】字符串S = aa
我们的for循环代码是这样的

for(int i=0; i<2; i++) for(int j=0; j<2; j++) if(i!=j) printf("%c%c\n",S[i],S[j]);

这时候，输出结果是这样的

aa aa

也就是说会出现重复，所以我们发现了，在一层循环中，相同的字符会产生出相同的字符串，因此我们会对上面的代码这样修改

for(int i=0; i<2; i++) { if(i>0 && S[i]==S[i-1]) continue for(int j=0; j<2; j++) { if(j>0 && S[j]==S[j-1] && j-1!=i) //j-1!=i表示上一个字符并没有被前面一层循环使用时 continue; if(i!=j) printf("%c%c\n",S[i],S[j]); } }

这样输出结果就是

aa

根据这一思路，我们就可以用递归来解决这个问题，首先，我们要定义

boolean used[] //表示一个字符是否被使用，因为是在递归里，不能像for循环一样来规避相同位置的元素

完整代码：

import java.util.List; import java.util.ArrayList; import java.util.Arrays; class Solution { public String[] permutation(String S) { List res = new ArrayList(); int len = S.length(); if (len == 0) return new String[0]; boolean[] used = new boolean[len]; char[] sChar = S.toCharArray(); StringBuilder path = new StringBuilder(len); // 排序是为了后面的剪枝。其实剪枝就是我们for循环里边避免重复操作的那一步 Arrays.sort(sChar); dfs(res, sChar, len, path, 0, used); return res.toArray(new String[0]); }/** * @param res 结果集 * @param sChar 输入字符数组 * @param len 字符数组长度 * @param path 根结点到任意结点的路径 * @param depth 当前树的深度 * @param used 使用标记数组 */ private void dfs(List res , char[] sChar , int len , StringBuilder path , int depth , boolean[] used) { // 到达叶子结点 if (depth == len) { res.add(path.toString()); return; }for (int i = 0; i < len; i++) { if (!used[i]) {// 根据已排序字符数组, 剪枝 if (i > 0 && sChar[i] == sChar[i-1] && !used[i-1]) { continue; }path.append(sChar[i]); used[i] = true; // 标记选择 dfs(res, sChar, len, path, depth+1, used); path.deleteCharAt(depth); used[i] = false; // 撤销选择 } } } }

解法来源作者：miracle-131
链接：https://leetcode-cn.com/problems/permutation-ii-lcci/solution/hui-su-suan-fa-jian-zhi-9980-10000-by-miracle-131/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。