有一個經典題目:從一組字串中,找出那些「只是字元順序不同」的元素。例如給定 [ 'abcd', 'hello', 'bdca', 'olleh', 'cadb', 'nba', 'abn', 'abc' ],要挑出 [ 'abcd', 'bdca', 'cadb' ]。關鍵在於如何判斷兩個字串是否由相同字元組成。
遍歷每個字串的所有字元,把它們的 Unicode 編碼加總。由於 abcd 與 bdca 的字元相同,編碼和會一致,於是就能用這個和當作分組的 key。
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;
for( j = 0; j < strLength; j++ ){ num += item.charCodeAt( j ); }
if( !firstItem ){ firstItem = item; obj[ num ].push( item ); }
else if( ~firstItem.indexOf(item.charAt(0)) ){ obj[ num ].push( item ); }
}
for( name in obj ){ console.log( obj[name] ); }
};
要注意的是,像 'ad' 與 'bc' 的編碼和可能相同,因此還需多一個判斷:檢查其中一個字串的首字元是否有出現在另一個裡。
把字串轉成陣列、排序、再拼回字串。這樣 abcd 與 bdca 排序後都會變成 abcd,用排序後的結果當 key 分組即可:
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] ); }
};
兩種方法的原理其實相通,都是把字元正規化:方法一顯式地轉成 Unicode 編碼,方法二則靠 sort 隱式地進行比較排序。方法二寫起來更直覺,也少了碰撞的顧慮。