萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 從陣列中找出字元順序不同但組成相同的字串分組(字母異位詞分組)

問題定義

給定字串陣列 ['abcd', 'hello', 'bdca', 'olleh', 'cadb', 'nba', 'abn', 'abc'],找出由相同字元組成、順序不同的分組。預期輸出:[['abcd','bdca','cadb'], ['hello','olleh']](單獨字串不成組可選擇過濾)。

方法一:字元編碼和分組(原文方案)

function groupByCharCodeSum(arr) {
  const groups = {};
  let firstItem = null;

  for (const item of arr) {
    // 計算 Unicode 編碼和
    let sum = 0;
    for (let i = 0; i < item.length; i++) {
      sum += item.charCodeAt(i);
    }

    // 初始化基準字串
    if (!firstItem) {
      firstItem = item;
      groups[sum] = [item];
      continue;
    }

    // 關鍵去重:檢查首字符是否出現在基準字串中
    // 避免 'ad'(97+100=197) 與 'bc'(98+99=197) 編碼和相同但字元不同的誤判
    if (firstItem.includes(item[0])) {
      (groups[sum] = groups[sum] || []).push(item);
    }
  }

  // 返回長度>1的分組
  return Object.values(groups).filter(g => g.length > 1);
}

缺點:編碼和碰撞概率極高(如 'ad' === 'bc'),需額外檢查首字符,仍不完全可靠(如 'ace' vs 'bdf' 可能同和)。

方法二:字元排序標準化(推薦、穩健)

function groupBySortedChars(arr) {
  const groups = {};
  for (const item of arr) {
    // 將字串拆字元、排序、重組作為鍵
    const key = item.split('').sort().join('');
    (groups[key] = groups[key] || []).push(item);
  }
  // 可選:只返回分組數>1的
  return Object.values(groups).filter(g => g.length > 1);
}

// 測試
const arr = ['abcd', 'hello', 'bdca', 'olleh', 'cadb', 'nba', 'abn', 'abc'];
console.log(groupBySortedChars(arr));
// [ ["abcd", "bdca", "cadb"], ["hello", "olleh"] ]

優點:

  • 字元排序後相同 ⇔ 字元組成完全相同(含重複字元次數),數學上嚴格等價。
  • 無碰撞風險,邏輯清晰,易維護。
  • 時間複雜度 O(N * L log L)(L 為字串長度),對短字串極快。

方法三:字元頻率統計(線性時間,適合超長字串)

function groupByFrequency(arr) {
  const groups = {};
  for (const item of arr) {
    const freq = new Array(26).fill(0); // 假設僅小寫字母
    for (const ch of item) {
      freq[ch.charCodeAt(0) - 97]++;
    }
    const key = freq.join('#'); // 頻率陣列序列化為鍵
    (groups[key] = groups[key] || []).push(item);
  }
  return Object.values(groups).filter(g => g.length > 1);
}

時間複雜度 O(N * L),空間換時間,適合長字串、大數據量場景。

擴展:Unicode 字元(含中文、Emoji)支援

function groupBySortedUnicode(arr) {
  const groups = {};
  for (const item of arr) {
    // 使用展開運算符正確處理代理對
    const key = [...item].sort().join('');
    (groups[key] = groups[key] || []).push(item);
  }
  return Object.values(groups).filter(g => g.length > 1);
}

// 測試中文
console.log(groupBySortedUnicode(['你好', '好你', '世界', '界世']));
// [ ["你好", "好你"], ["世界", "界世"] ]

效能對比(百萬級數據參考)

方法時間複雜度適用場景
編碼和+首字符檢查O(N*L)不推薦,易碰撞
字元排序O(N * L log L)通用首選,短字串極快
頻率統計O(N * L)長字串、大數據、固定字符集

總結

尋找「字元組成相同、順序不同」的字串分組,本質是字母異位詞分組。字元排序法以其簡潔、正確、無碰撞成為標準解法。原文「編碼和」方案雖有巧思,但因碰撞風險不適合生產環境。實際開發中,根據字串長度、字符集範圍選擇排序法或頻率法即可。

copyright © 萬盛學電腦網 all rights reserved