生态建设研究所网站,蛇口网站建设,网站建设过程规划和准备阶段,网站建设技术解决方案题目描述#xff1a;
无重复字符串的排列组合。编写一种方法#xff0c;计算某字符串的所有排列组合#xff0c;字符串每个字符均不相同。
示例1: 输入#xff1a;S qwe 输出#xff1a;[qwe, qew, wqe, weq
无重复字符串的排列组合。编写一种方法计算某字符串的所有排列组合字符串每个字符均不相同。
示例1: 输入S qwe 输出[qwe, qew, wqe, weq, ewq, eqw] 示例2: 输入S ab 输出[ab, ba] 提示:
字符都是英文字母。 字符串长度在[1, 9]之间。 思路
逐个位置进行选择一个位置选择了字符后后面位置不能再选择这个字符可以用set进行去重.
**代码
class Solution {public String[] permutation(String ab) {if(ab null) {return new String[0];}SetString r new HashSet();char[] c ab.toCharArray();boolean[] used new boolean[ab.length()];recursion(r, c, used, new StringBuilder());String[] re new String[r.size()];int i 0;for (String s:r) {re[i] s; }return re;}private static void recursion(SetString r, char[] c, boolean[] used, StringBuilder s) {if(s.length() c.length) {r.add(new String(s));return;}for (int i 0; i c.length; i) {if(!used[i]) {used[i] true;s.append(c[i]);recursion(r, c, used, s);s.deleteCharAt(s.length() -1);used[i] false;}}}
} **思路二** 仔细观察可以发现求不同全排列的问题其实是可以利用交换字符串元素来完成的
若字符串长度为n将第一个字母分别与后面每一个字母进行交换生成n种不同的全排列再用第二个元素与后面每一个元素进行交换生成n - 1种不同的全排列…… public static String[] permutation(String S) {char[] chs S.toCharArray();SetString list new HashSet();backtrack(chs, 0, list);return list.toArray(new String[list.size()]);}private static void backtrack(char[] chs, int idx, SetString list) {if (idx chs.length - 1) {list.add(new String(chs));return;}for (int i idx; i chs.length; i) {char tmp chs[idx];chs[idx] chs[i];chs[i] tmp;backtrack(chs, idx 1, list);tmp chs[idx];chs[idx] chs[i];chs[i] tmp;}}
