FreeCodeCamp

No repeat please(196)

• 把一个字符串中的字符重新排列生成新的字符串
• 返回新生成的字符串里没有连续重复字符的字符串个数

• 连续重复只以单个字符为准

  eg. aab 应该返回2， 因为总共有6种排列(aab,aab,aba,aba,baa,baa)，只有aba,aba合符标准

---

分析

首先将该字符串转换成数组

var a = str.split('');

运用全排列算法，来算出全排列的结果， 现在我们具体来分析如何实现该算法。

eg. abc 应该返回2，因为总共有6种排列(bac, cba, acb, bca, cba, abc)

bac, cba 都是 abc 的 a与后面两个字符替换得到的
acb 是将 abc 第二个字符和第三个字符交换可得到
bca 则是由 bac 的第二个和第三个字符交换得到
同理可知， cab 亦是由 cba 交换而来的

结论：因此可以知道全排列算法即是从第1个数开始，分别与后面的数进行交换的过程，其复杂度为O(n!)，用递归算法可以较轻易实现

function generate(start) {
    if(start === arr.length-1)
	{
		permutation.push(arr.join(''));
	}
	else
	{
		for(var i = start;i <= arr.length-1;i++)	
		{	//从下标为start的数开始，分别与它后面的数字交换
			swap(start,i); 
			generate(start+1);
			swap(start,i); 
		}
	}
  }
  generate(0);

其次运用 正则表达式 /(.)\1+/g来判断诸如aab之类的字符串

function permAlone(str) {
  var regex = /(.)\1+/g,//匹配重复字母，\1表示后面紧跟的字符
      arr = str.split(''),
      permutation = [];
  
  if(str.match(regex)!==null&&str.match(regex)[0]===str)//看是不是只有aaaa之类的单词
    return 0;
  
  function swap(a,b){
    var temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }
  
  //堆全排列算法
  //https://en.wikipedia.org/wiki/Heap's_algorithm
  function generate(start) {
    if(start === arr.length-1)
	{
		permutation.push(arr.join(''));
	}
	else
	{
		for(var i = start;i <= arr.length-1;i++)	
		{	//从下标为start的数开始，分别与它后面的数字交换
			swap(start,i); 
			generate(start+1);
			swap(start,i); 
		}
	}
  }
  
  generate(0);
  
  var filtered = permutation.filter(function(string){
    return !string.match(regex);
  });
  
  return filtered.length;
}

permAlone('abcdefa');