[关闭]
@yexiaoqi 2022-05-12T02:47:41.000000Z 字数 851 阅读 318

面试题 08.08. 有重复字符串的排列组合

刷题 leetcode


题目:有重复字符串的排列组合。编写一种方法,计算某字符串的所有排列组合。
示例1:

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

示例2:

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

提示:
1. 字符都是英文字母。
2. 字符串长度在[1, 9]之间。

链接:https://leetcode-cn.com/problems/permutation-ii-lcci


面试题 08.07. 无重复字符串的排列组合思路类似,只是多了一步去重

  1. public class Main {
  2. List<String> list = new ArrayList<>(); //存放单词的所有排列组合结果集
  3. public String[] permutation(String S) {
  4. char[] chars = S.toCharArray();
  5. //如果要求字典序,对chars数组提前排序Arrays.sort(chars) || 最后对list结果集排序 list.sort(null)
  6. backtrack(chars, 0);
  7. return list.toArray(new String[0]);
  8. }
  9. //c:单词的字符数组 k:要交换的元素下标
  10. private void backtrack(char[] c, int k) {
  11. if(k == c.length-1){
  12. list.add(new String(c));
  13. return;
  14. }
  15. Set<Character> set = new HashSet<>();
  16. for(int i=k; i<c.length; i++){
  17. //通过字符数组中相同的字母只取第一个来去重
  18. if(!set.contains(c[i])) {
  19. set.add(c[i]);
  20. swap(c, i, k); //交换
  21. backtrack(c, k+1); //回溯
  22. swap(c, i, k); //还原
  23. }
  24. }
  25. }
  26. private void swap(char[] c, int i, int j) {
  27. char temp = c[i];
  28. c[i] = c[j];
  29. c[j] = temp;
  30. }
  31. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注