题目链接

无重复字符串的排列组合

题目描述

注意点

• 字符都是英文字母
• 字符串长度在[1, 9]之间
• 字符串每个字符均不相同

解答思路

• 字符串中有n个字符，则其排列组合的数量为n * (n - 1) * (n - 2) * … * 1
• 可以深度优先遍历找到字符串的所有排列组合，且需要将前面已经用过的字符记录下来传入到下一层中，并在本次深搜全部完成后进行回溯（在stringbuilder中删除该字符，更新该字符为未使用过）

代码

class Solution {int n;int idx;public String[] permutation(String s) {n = s.length();idx = 0;int sum = 1;for (int i = 1; i <= n; i++) {sum *= i;}String[] res = new String[sum];boolean[] visited = new boolean[n];dfs(s, 0, visited, new StringBuilder(), res);return res;}public void dfs(String s, int depth, boolean[] visited, StringBuilder sonRes, String[] res) {if (depth >= n) {res[idx] = sonRes.toString();idx++;return;}for (int i = 0; i < n; i++) {if (visited[i]) {continue;}sonRes.append(s.charAt(i));visited[i] = true;dfs(s, depth + 1, visited, sonRes, res);sonRes.deleteCharAt(sonRes.length() - 1);visited[i] = false;}}
}

关键点

• 深度优先遍历的思想