剑指27 字符串的全排列【一种易理解方法】

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

思路：假设字符串一共有10个字符，按排列组合的常规思路（不考虑重复字符的情况），先确定第一个位置，然后第二个位置,...,那么第一个位置有10种可能，第二个位置有9种可能，依次类推，可知所有情况数为10！。具体来说，当第一个位置的字符确定后，则原字符串中该字符不应被后面位置所考虑，同理，当前面n个位置的字符确定后，则原字符串中的这些字符不能在被后面位置所考虑。那样怎样才能知道哪些字符已经被用过了呢？方法是通过一个数组来记录，该数组长度和原字符串相同，初始化值全为1，当字符串中某个位置的字符被加到子串中时，将其对应的数组元素置为0，当该字符又可以被加到字串中时，其对应数组元素再被置为1（像是开关）。另外，为了防止重复串的出现，对于新串的每个位置，通过set记录已被选择过的字符，后面该位置新添的字符不能出现set中。通过递归来实现每个位置的字符的选取（像是深度优先搜索），最后对结果数组进行排序，保证字典序。代码如下：

function help(rst, str, strCur, accessList){
  if (strCur.length == str.length){
      rst.push(strCur);
      return;
  }
  let set = new Set();
  for (let i = 0; i < str.length; ++i) {
      if (accessList[i] && !set.has(str[i])){
          accessList[i] =0;
          set.add(str[i]);
          help(rst, str, strCur + str[i], accessList);
          accessList[i] = 1;
      }
  }
}
function Permutation(str)
{
    // write code here
    let rst = [];
    if (!str.length) return rst;
    let accessList = new Array(str.length).fill(1);
    help(rst, str, "", accessList);
    return rst.sort();
}

扩展

思考：上面的解法中，通过一个和原字符串相同长度的数组来记录当前哪些位置的字符已经被用过了，那么在不另开辟空间的条件下，有办法来避开前面已经用过的字符吗？一个直接的方法是当某个字符用过后，将删除改字符的新的字符串传入下次迭代中， 参考了“一颗闪闪发亮的马路星”， 代码如下：

function help(rst, str, strCur){
  if (!str){
      rst.push(strCur);
      return;
  }
  let set = new Set();
  for (let i = 0; i < str.length; ++i) {
      if (!set.has(str[i])){
          set.add(str[i]);
          let strNext = str.substring(0, i) + str.substring(i + 1);
          help(rst, strNext, strCur + str[i]);
      }
  }
}

function Permutation(str)
{
    // write code here
    let rst = [];
    if (!str.length) return rst;
    help(rst, str, "");
    return rst.sort();
}

扩展2

思考：上述第一个方法需要额外的数组来记录哪些位置的字符已经被用过，第二个方法通过构造新的字符串来保证后面位置的字符不会是前面用到的，那有可以直接在原字符串上操作的方法吗？即不需要额外的数组也不需要构造新字符串。牛客官方题解给出了方法，其本质和上述两个方法一致，就是在先确定前面位置的字符，后面位置的字符从剩余字符中选择组合，不同点在于，其通过交换两个字符位置的方法实现了所有可能字符的选择和避免已经选择的字符再被选择，可谓一举两得，非常精妙，c++中的swap函数可以直接交换字符串中的两个字符，js没法改变原字符串，所以转为数组来做，最后再将数组转为字符串。代码如下：

function help(rst, arr, pos){
  if (pos == arr.length - 1) {
    rst.push(arr.join(""));
    return;
  }

  let set = new Set();
  for (let i = pos; i < arr.length; ++i) {
    if (!set.has(arr[i])){
      set.add(arr[i]);
      let cache = arr[pos];
      arr[pos] = arr[i];
      arr[i] = cache;
      help(rst, arr, pos+1);
      arr[i] = arr[pos];
      arr[pos] = cache;
    }
  }
}

function Permutation(str)
{
    // write code here
    let rst = [];
    if (!str.length) return rst;
    let arr = str.split("");
    help(rst, arr, 0);
    return rst.sort();
}