字符串的排列(回溯)

  • Post author:
  • Post category:其他



题目:


输入一个字符串,打印出该字符串中字符的所有排列。


例子:


在这里插入图片描述

总而言之,就是不带重复的排列组合。


代码1:(回溯):

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

class Solution {
    //用来放所有可能的排列
    private List<String> list = new LinkedList();

    //将String s 转换为char[],当作全局变量,方便调换值
    private char[] s_char;

    public String[] permutation(String s) {
        this.s_char = s.toCharArray();
        doPermutation(0);
        return list.toArray(new String[list.size()]);
    }

    private void doPermutation(int x){
        //如果到了最后一位,就终止当前递归,并添加值。
        if (x == s_char.length-1){
            list.add(String.valueOf(s_char));
            return;
        }
        //HashSet主要是防止重复的值,例如abbc,这两个b其中取一个就够了。
        HashSet<Character> set = new HashSet<>();
        for (int i = x; i < s_char.length; i++){
            //判断是否重复
            if (set.contains(s_char[i])) continue;
            set.add(s_char[i]);

            //先调换,再递归,再还原,老回溯算法了
            swap(i, x);
            doPermutation(x+1);
            swap(i, x);
        }
    }

    //调换值
    private void swap(int a, int b){
        char temp = s_char[a];
        s_char[a] = s_char[b];
        s_char[b] = temp;
    }
}


代码1解释:


回溯算法的经典思路就是改变现场,递归循环,还原现场。之前另外一道题就是树的回溯,题目是【找和为某值的树的所有路径节点】。

这个算法给出String 10个字符,返回结果90多万个排列,可怕。



版权声明:本文为weixin_44007213原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。