【FCC】No repeats please

题目:

把一个字符串中的字符重新排列生成新的字符串,返回新生成的字符串里没有连续重复字符的字符串个数.连续重复只以单个字符为准

例如, aab 应该返回 2 因为它总共有6中排列 (aab, aab, aba, aba, baa, baa), 但是只有两个 (aba and aba)没有连续重复的字符 (在本例中是 a).

示例:

permAlone(“aab”) 应该返回一个数字.
permAlone(“aab”) 应该返回 2.
permAlone(“aaa”) 应该返回 0.
permAlone(“aabb”) 应该返回 8.
permAlone(“abcdefa”) 应该返回 3600.
permAlone(“abfdefa”) 应该返回 2640.
permAlone(“zzzzzzzz”) 应该返回 0.

思路:

首先,把第一个字符和其后面的字符一一交换。

接着,固定第一个字符,求后面所有字符的排列。这个时候我们仍把后面的所有字符分成两部分:后面字符的第一个字符,以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换。

去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。

代码:

<script type="text/javascript">
	function permAlone(str) {
		var arr = str.split("");
		var perarr = [];
		var begin = 0;
		//创建正则,如果字符串全重复,则直接return 0
		var reg = /(.)\1+/g; //括号里面的代表分组,\1表示获得和第一个分组里完全相同的内容,也就是匹配任意连续的字符

		//如果字符全部重复,直接返回0
		// if(arr.every(function(val){return val===arr[0];})){
		// return 0;
		// }
		//推荐以下方法
		if (str.match(reg) !== null && str.match(reg)[0] === str) {
			return 0;
		}
		//用于交换的函数
		function swap(index1, index2) {
			var temp = arr[index1];
			arr[index1] = arr[index2];
			arr[index2] = temp;
		}
		//如果begin到了最后一个字符,可以将这个字符串加入到全排列数组中了
		function permall(arr, begin) {
			if (begin == arr.length - 1) {
				perarr[perarr.length] = arr.join("");
				// console.log(perarr);

				return;
			}
			console.log(arr.length);
			for (var i = 0;
				(i + begin) < arr.length; i++) {
				// console.log('begin:'+begin);
				// console.log('begin+i:'+(begin+i));
				swap(begin, begin + i);
				// console.log(arr);
				permall(arr, begin + 1);
				// console.log('begin:'+begin);
				// console.log('begin+i:'+(begin+i));
				swap(begin, begin + i);

			}
		}
		// console.log('arr:'+arr);
		// console.log('begin:'+begin);

		permall(arr, begin);
		//返回相邻不重复的数量
		console.log('结束后:' + perarr);
		return perarr.filter(function(val) {
			// console.log(val);
			// console.log(reg);
			return !val.match(reg);
		}).length;
	}
</script>

 

转自:http://www.bubuko.com/infodetail-1846458.html

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注