給定字串陣列 ['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),空間換時間,適合長字串、大數據量場景。
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) | 長字串、大數據、固定字符集 |
尋找「字元組成相同、順序不同」的字串分組,本質是字母異位詞分組。字元排序法以其簡潔、正確、無碰撞成為標準解法。原文「編碼和」方案雖有巧思,但因碰撞風險不適合生產環境。實際開發中,根據字串長度、字符集範圍選擇排序法或頻率法即可。