MediumRating 1530

1657. Determine if Two Strings Are Close

hash-tablestringsortingcounting

解題說明

Determine if Two Strings Are Close

題目描述：給定兩個字串 word1 和 word2，判斷它們是否「接近」。可以對字串執行以下兩種操作任意次：(1) 交換任意兩個字元的位置（anagram 操作）；(2) 將字串中所有出現的字元 x 替換成 y，同時將所有 y 替換成 x（雙向互換）。若能透過這些操作將 word1 變成 word2，則兩者「接近」。

解題思路：

關鍵在於理解這兩種操作的本質：

操作一（位置交換）：不改變任何字元的出現頻率，只調整排列順序。
操作二（字元互換）：不改變頻率的「多重集合」（multiset），只是把頻率值重新分配給不同字元。

因此，兩個字串「接近」的充要條件為：

字元集合相同：word1 和 word2 使用的字元種類必須完全一致。若 word1 含有 word2 沒有的字元，操作二無法憑空產生新字元，故永遠無法對齊。
頻率多重集合相同：將兩字串各字元的出現頻率分別收集成多重集合後排序，兩者必須完全相同。操作二只能「交換」頻率值，不能改變頻率的組成。

實作上，統計兩個字串的字元頻率後，比較：(a) 兩者的 key set 是否相等；(b) 將頻率 value 排序後是否相等。

C++ 解法

複雜度分析

時間複雜度：O(n + 26 log 26) = O(n) — 遍歷兩個字串各需 O(n) 建立頻率陣列；對大小固定為 26 的陣列排序為常數時間 O(26 log 26)。整體由字串長度 n 主導。

空間複雜度：O(1) — 只使用兩個大小固定為 26 的整數陣列，不隨輸入規模增長。

虛擬碼

1. If len(word1) != len(word2), return false
2. Build frequency arrays freq1[26] and freq2[26]
   a. For each char c in word1: freq1[c - 'a']++
   b. For each char c in word2: freq2[c - 'a']++
3. Check character set equality
   a. For i in 0..25:
      - If (freq1[i] == 0) XOR (freq2[i] == 0): return false
4. Sort both frequency arrays
5. Return freq1 == freq2

其他解法

方法二：使用 unordered_map O(n)：以 unordered_map<char, int> 取代固定大小陣列儲存頻率，邏輯完全相同。優點是語意更清晰，缺點是 hash map 的常數因子較大，且對於只含小寫字母的問題而言，固定陣列更簡潔高效。

方法三：排序比較 O(n log n)：直接將兩個字串排序後比較是否相等，可驗證 anagram 條件（操作一），但無法單獨處理操作二。需搭配字元集合檢查才能完整判斷。此做法時間複雜度較高（O(n log n)），且邏輯較不直觀，不如頻率多重集合方法直接。

延伸思考

若加入第三種操作：可以刪除字串中任意一個字元，兩字串「接近」的判斷條件應如何修改？哪些原有的必要條件會因此放寬？
本題的操作二要求雙向同時互換（x↔y）。若改為單向替換（將所有 x 換成 y，但 y 不變），充要條件會有何不同？頻率多重集合的等價性是否仍然成立？
將問題推廣到 k 個字串（k > 2）：如何在 O(k·n) 的時間內判斷所有字串是否兩兩「接近」？是否需要對每對字串都執行一次比較，還是存在更有效率的方式？