LeetCode 剑指offer Q38字符串的排列
程序员文章站
2024-01-22 11:06:40
...
思路
求一个字符串的全排列组合,直接想到使用回溯中的全排列算法。
回顾一下全排列算法:
假设 需要排列 abc。
下图表示了整个递归过程。对abc进行全排列就是有三个位置用abc去填,全排列算法使用交换来实现填入操作。如图,第一层递归拿到abc,固定住第一个元素,然后使用循环的方式分别将后面的每个元素和第一个元素进行交换,这样一次层递归便将第一个位置的字母确定了,然后进入在循环中进入下一层递归去确定下一个位置的元素,这样直到到达最后一个元素时,将此次序列输出,顺便进行去重操作。
代码
package algorithm.jianzhiOffer;
import java.util.*;
public class Q38 {
List<String> res;
Set<String> a;
int len;
public String[] permutation(String s) {
len = s.length();
a = new HashSet<>();
res = new ArrayList<>();
String[] ss = s.split("");
sub(ss, 0);
return res.toArray(ss);
}
void sub(String[] s, int k) {
if (k == len-1) {
StringBuffer re = new StringBuffer();
for (String ch : s)
re.append(ch);
if (!a.contains(re.toString())) {
res.add(re.toString());
a.add(re.toString());
}
} else {
for (int i = k; i < len; i++) {
swap(s, k, i);
sub(s, k+1);
swap(s, k, i);
}
}
}
void swap(String[] s, int i, int j) {
String temp = s[i];
s[i] = s[j];
s[j] = temp;
}
public static void main(String[] argc) {
String[] qq=new Q38().permutation("adbc");
return;
}
}
上一篇: leetcode 401: 二进制手表
推荐阅读
-
LeetCode 剑指offer Q38字符串的排列
-
【Leetcode每日笔记】剑指 Offer 47. 礼物的最大价值(Python)
-
剑指offer27:按字典序打印出该字符串中字符的所有排列
-
剑指Offer-24——字符串的排列
-
20200329-剑指offer-面试题48. 最长不含重复字符的子字符串(滑动窗口)
-
leetcode 160剑指offer面试题52. 两个链表的第一个公共节点(python3)
-
leetcode中剑指offer的习题 C++语言实现(2)
-
leetcode 113 剑指offer 面试题34. 二叉树中和为某一值的路径(python3)
-
leetcode中剑指offer的习题 C++语言实现(1)
-
剑指offer两个面试案例 把字符串转换成整数 树中两个节点的最低公共祖先