題目描述:給定兩個字串 word1 和 word2,判斷它們是否「接近」。可以對字串執行以下兩種操作任意次:(1) 交換任意兩個字元的位置(anagram 操作);(2) 將字串中所有出現的字元 x 替換成 y,同時將所有 y 替換成 x(雙向互換)。若能透過這些操作將 word1 變成 word2,則兩者「接近」。
解題思路:
關鍵在於理解這兩種操作的本質:
因此,兩個字串「接近」的充要條件為:
word1 和 word2 使用的字元種類必須完全一致。若 word1 含有 word2 沒有的字元,操作二無法憑空產生新字元,故永遠無法對齊。實作上,統計兩個字串的字元頻率後,比較:(a) 兩者的 key set 是否相等;(b) 將頻率 value 排序後是否相等。
時間複雜度: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)),且邏輯較不直觀,不如頻率多重集合方法直接。