JavaScript算法题之–查找不同顺序排列的字符串

需求描述:从一组数组中找出一组按不同顺序排列的字符串的数组元素。假如有这样一个数组:


var arr1 = [ 'abcd', 'hello', 'bdca', 'olleh', 'cadb', 'nba', 'abn', 'abc' ];

需要找出的结果是:


var arr2 = [ 'abcd', 'bdca', 'cadb' ];

那么这里的关键点是判断一组字符串是否是否只是字符的顺序不同,只要解决整个关键点其他都好办了。

方法1:


var stringClassify = function( arr ){
	var arrLength = arr.length,
		obj = {},
		i = 0,
		num, item, name, firstItem, strLength;

	for( ; i < arrLength; i++ ){
		item = arr[i];
		strLength = item.length;
		num = 0;

		// 将单个的字符转换成 Unicode 编码
		// 对编码进行取和计算
		for( j = 0; j < strLength; j++ ){
		    num += item.charCodeAt( j );
		}		

		if( !firstItem ){
		    firstItem = item;
		    obj[ num ].push( item );
		}
                // 通过检测待添加的字符串的第一个字符是否
                // 在另一个字符串中出现以避免将下面的情况
                // [ 'ad', 'da', 'bc' ]
		else if( ~firstItem.indexOf(item.charAt(0)) ){
		    obj[ num ].push( item );
		}
	}

	for( name in obj ){
		console.log( obj[name] );
	}
};	

方法1采用了遍历字符串中的每一个字符,然后将单个的字符转换成 Unicode 编码,对编码进行取和的计算,abcd 和 bdca 的编码和会是一致的。最后用编码和作为对象的 key 来保存编码和一致的字符串。

方法 1 需要注意的是,字符串“ad”和“bc”的 Unicode 编码和是一样的,此时需要多加一个判断,检测任意一个字符串中的第一个字符是否有出现在另一个字符串中出现过即可。

方法2:


var stringClassify = function(){
	var arrLength = arr.length,
		obj = {},
		i = 0,
		num, item, name, strArr, newStr;

	for( ; i < arrLength; i++ ){
		item = arr[i];

		strArr = arr[i].split( '' );
		strArr.sort();
		newStr = strArr.join( '' );

		if( !obj[newStr] ){
			obj[ newStr ] = [];
		}

		obj[ newStr ].push( item );
	}

	for( name in obj ){
		console.log( obj[name] );
	}
};

方法2是将字符串转换成数组后再对数组进行 sort 排序,abcd 和 bdca 使用 sort 排序后会变成 abcd,将拍好序的字符串作为对象的 key 来保存排序一致的字符串。

其实两种方法的原理都是通过将字符转换成 Unicode 编码,只是方法1是显式的转换,而方法2中用到的 sort 排序,会隐式的转换。

原载于:雨夜带刀's Blog
本文链接:http://stylechen.com/full-array-classify.html
如需转载请以链接形式注明原载或原文地址。

“JavaScript算法题之–查找不同顺序排列的字符串”目前已有 11 条评论

  • *
  • *

评论列表

  • 小子说道:

    第一个方法求和,不会遇到碰撞么

  • 雨夜带刀说道:

    @小子
    暂时还没发现问题,能举个栗子吗?

  • tdwyx说道:

    @雨夜带刀
    [‘ad’, ‘da’, ‘bc’] 这个样子的

  • 雨夜带刀说道:

    @小子 @tdwyx
    谢谢二位的提醒,多加了一层判断,已修正。

  • 人间清暑殿说道:

    方法一是行不通的,原因是一组数的和相同,不能说明这是一组相同的数。比如:2+2=4,1+3=4。即使限定一组数是不重复的,也不行,比如:5+2=7,4+3=7。
    修正版无法解决上面所说的问题,而且带来了新的问题。
    一些情况下,会使一些应该统计的字符串被扔掉,比如:[‘ad’, ‘da’, ‘bc’,’cb’] 。
    一些情况下,仍然把不同的字符组统计在了一起,比如:[ ‘ead’, ‘eda’, ‘ebc’, ‘ecb’];
    关键是会扔掉[ ‘abcd’, ‘hello’, ‘bdca’, ‘olleh’, ‘cadb’, ‘nba’, ‘abn’, ‘abc’ ]这里里面的hello和olleh。
    最极端的是[ ‘f’, ‘hello’, ‘bdca’, ‘olleh’, ‘cadb’, ‘nba’, ‘abn’, ‘abc’ ],除了第一个都会被扔掉
    另外修正版少了
    if(!obj[num]) obj[ num ] = [];这句,程序运行就会报错。

  • 阿安说道:

    还有个正则的思路,呵呵。。
    var arr = [ ‘abcd’, ‘hello’, ‘bdca’, ‘olleh’, ‘cadb’, ‘nba’, ‘abn’, ‘abc’, ‘aaa’, ‘aaaaa’, ‘bbaaaaab’ ]

    function find(val, arr) {
    var result = [], i = arr.length; reg = eval(‘/^[‘+val+’]{‘ + val.length +’}$/’);
    while(–i >=0){
    reg.test(arr[i]) && result.push(arr[i]);
    }
    return result;
    }

    console.log(find(‘abcd’, arr));

  • 米空格说道:

    尝试分组处理

    var arr = [],
    length = 107,
    i = 0;

    for( ; i 0) {
    len -= 1;
    }

    var tmpInx, baseInx = 0;

    for(var i=0;i 0) {
    tmpInx = baseInx + parseInt(Math.random() * (arrLen – baseInx));

    ret[len – 1] = arr[tmpInx];
    }

    return ret;
    }

    console.log(getRndArr(arr, 10));

  • bukas说道:

    不错不错

  • 中传思客说道:

    function likeSort(arg){
    var obj={},key,t;
    while(t=arg.pop()){
    key=[].sort.apply(t.split(”)).join(”);
    obj[key]=obj[key]?obj[key].concat(t):[t];
    }
    return obj;
    }

  • […] (准备面试,多看点题。来自雨夜带刀’s Blog ) […]