[关闭]
@yexiaoqi 2022-05-12T02:47:55.000000Z 字数 781 阅读 306

面试题 08.07. 无重复字符串的排列组合

刷题 leetcode


题目:无重复字符串的排列组合。编写一种方法,计算某字符串的所有排列组合,字符串每个字符均不相同。

示例1:

输入:S = "qwe"
输出:["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

示例2:

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

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

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


  1. class Solution {
  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(S.toCharArray(), 0);
  7. return list.toArray(new String[list.size()]);
  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. for(int i=k; i<c.length; i++){
  16. swap(c, i, k);//交换
  17. backtrack(list, c, k+1);//回溯
  18. swap(c, i, k);//还原
  19. }
  20. }
  21. private void swap(char[] c, int i, int j){
  22. char temp = c[i];
  23. c[i] = c[j];
  24. c[j] = temp;
  25. }
  26. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注