2021年3月15日 字符串排列 回溯算法

输入一个字符串,按字典序打印出该字符串中字符的所有排列。
例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc, acb,bac, bca , cab和cba.

思路:使用回溯法.
记录一个字符(temp) ,用于存储当前需要进入排列的字符
记录一个字符串(current) ,用于记录当前已经排列好的字符
*记录一个队列(queue) ,用于存储还未被排列的字符

1.每次排列将temp添加到current.
2,如果queue为空,则本次排列完成,将curret加入到结果数组中,结束递归如果queue不为空,说明还有未排列的字符.
3,递归排列queue中剩余的字符.

为了不影响后续排列,每次递归完成,将当前递归的字符temp加回队列

let a = '123';
function foo(str){
    if(typeof(str) != 'string'){
      return '不想转类型了,可以写转换类型的方法'
  }
  let data= [...str];
  function fn(data,arr){
      if(data.length == arr.length){
        return console.log(arr.join());
    }
    // console.log(data)
    for(let i = 0;i < data.length;i++){
        if (arr.indexOf(data[i]) < 0){
            arr.push(data[i]);
            fn(data, arr);
            arr.pop();
        }
    }
  }
  fn(data,[]);
}
foo(a,[])