題目描述:判斷兩個字串 s 和 t 是否為變位詞(使用相同字元,順序不同)。
解題思路:最直接的方法:計算兩個字串中各字元的頻率,若完全相同則為變位詞。用一個大小為 26 的整數陣列:對 s 加一,對 t 減一;最後若陣列全為 0 則是變位詞。或者直接排序兩個字串比較,但需要 O(n log n) 時間。
時間複雜度:O(n) — 兩次線性掃描。
空間複雜度:O(1) — 固定大小的計數陣列(26 個字母)。
1. If len(s) != len(t): return false 2. Count[26] = 0 3. For c in s: count[c]++ 4. For c in t: count[c]--; if count[c] < 0: return false 5. Return true
排序 O(n log n):排序兩個字符串,比較是否相等 — 時間複雜度更差。
ASCII 值求和 O(n):計算兩個字符串的字符 ASCII 值之和 — 易被碰撞攻擊,不推薦。