LeetCode
面试题 08.08. 有重复字符串的排列组合
有重复字符串的排列组合。编写一种方法,计算某字符串的所有排列组合
示例1:
输入:S = "qqe"
输出:["eqq","qeq","qqe"]
示例2:
输入:S = "ab"
输出:["ab", "ba"]
解法:回溯法
解题思路: 首先,要求一个字符串的各种组合,我们第一个想法肯定是通过for循环,那么for循环的层数是多少勒,应该是该字符串的长度,然后通过for循环来进行匹配,但是,我们应该要注意一个问题,在进行排列组合的时候,可能会出现重复的字符串,比如说
字符串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<String> res = new ArrayList<String>();
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<String> 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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。