深度优先搜索_全排列问题
程序员文章站
2022-07-07 22:53:10
...
1 字符串的全排列
给定一组字符串,找出所有的排列组合数(有可能存在重复字符)。
思路:深度优先搜索,依然是套用搜索算法的模板,但是这里面涉及到重复字符,我们需要排除掉重复的字符串。这就涉及到剪枝问题。
上一张图:(借的大佬的)
对于如何深度搜索,当我们访问到某个节点时,我们以此节点开始,进行向后查找,我们固定住这个字符,然后重新进入。
此时为了避免重复,我们可以用set结构来去重。
依然是按照dfs的模板
class solution{
// 定义成全局变量,方便dfs的递归
char[] c;
List<String> res = new LinkedList<>();
public String[] permutation(String s) {
c = s.toString();
dfs(0);
return res.toArray(new String[res.size()]);
}
private void dfs(int count){
// DFS 确定停止条件
if(count == c.length-1){
// 长度等于字符串长度,说明此时已经拼凑出一种情况,可以返回
res.add(String.valueOf(c))
return;
}
// 用set存储重复
Set<Character> set = new HashSet<>();
for(int i=count; i<c.length; i++){
// set中存在,跳过,因为说明是重复的,即使现在交换;后面会出现重复情况
if(set.contains(c[i])){
continue;
}
set.add(c[i]); // 存进去
// 将该节点定住,
swap(i,count);
dfs(count+1);
// dfs 结束,要恢复成之前的状态
swap(i,count);
}
}
private void swap(int i,int count){
char tmp = c[i];
c[i] = c[count];
c[count] = tmp;
}
}
2 数字的全排列
与上面一题相同,leetcode 还有两道数字的全排列,分别是 LeetCode 46 和 LeetCode 47
LeetCode 46是不含重复数字的情况,会简单一些,那么我们就不需要考虑到去重,所以set结构就用不到
不带重复数字的全排列
class solution{
List<List<Integer>> res = new ArrayList<>();
int[] n;
public List<List<Integer>> permute(int[] nums) {
n = num;
dfs(0);
return res;
}
private void dfs(int count){
// dfs 确定停止条件
if(count == n.length-1){
res.add(toList(n));
return;
}
for(int i=count; i<n.length; i++){
swap(i,count);
// dfs
dfs(count+1);
// 恢复状态
swap(i,count);
}
}
// 数组转链表
private void List<Integer> toList(int[] n){
List<Integer> list = new ArrayList<>();
for(int num:n){
list.add(num;)
}
return list;
}
}