DIV CSS 佈局教程網

在陣列中找出「字母相同、順序不同」的字串
編輯:關於JavaScript     

需求描述

給定一組字串,把其中「由同一批字元以不同順序組成」的那些挑出來。例如:

[ 'abcd', 'hello', 'bdca', 'olleh', 'cadb', 'nba', 'abn', 'abc' ]

期望的結果是:

[ 'abcd', 'bdca', 'cadb' ]

關鍵在於如何判斷兩個字串是否只是字元順序不同。這個問題一旦解決,剩下的就是分組而已。

方法一:Unicode 編碼求和作為分組依據

把每個字元轉成 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 的計數陣列做更省記憶體的版本。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved