給定一組字串,把其中「由同一批字元以不同順序組成」的那些挑出來。例如:
[ '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;
// 將單一字元轉成 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] );
}
};
這個方法有一個必須補的破洞:'ad' 與 'bc' 的編碼總和恰好相同(97+100 = 98+99),單靠總和會誤判。因此要多加一層判斷——檢查任一組中某字串的首字元是否出現在另一個字串裡。嚴格說來,這只是降低碰撞機率的權宜之計,並非真正嚴謹。
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] );
}
};
把字串拆成陣列、排序、再合併,abcd 與 bdca 都會變成 abcd,以排序後的結果當 key 分組即可。
其實原理是共通的——都依賴字元順序不影響某個「特徵值」。差別只在方法一是顯式地做編碼轉換,方法二則由 sort 在比較時隱式地進行編碼轉換。實務上推薦方法二:程式碼更短、語意直白,而且不會有編碼總和碰撞的風險。唯一要留意的是它需要建立暫時陣列,在極大資料量下可考慮改用長度 26 的計數陣列做更省記憶體的版本。