題目描述:字串 t 是由 s 的所有字符打亂順序後,再隨機插入一個額外字符所得到的。找出這個被額外加入的字符並回傳。例如 s = "abcd",t = "abcde",則答案為 'e'。
解題思路:XOR 消去法。
t 比 s 多一個字符。若對 s 和 t 的所有字符做 XOR,s 中出現的字符在 t 中也出現(相同字符 XOR 後抵消為 0),最終剩下的就是那個額外加入的字符。
具體做法:初始化 result = 0,依次對 s 和 t 中所有字符的 ASCII 值做 XOR。由於 s 的字符在 t 中各出現一次(互相抵消),result 最終等於額外字符的 ASCII 值,轉回 char 即為答案。
這個方法只需要 O(n) 時間和 O(1) 空間,是最優雅的解法。
時間複雜度:O(n) — 分別遍歷 s(長度 n)和 t(長度 n+1),共 2n+1 次操作,為 O(n)。
空間複雜度:O(1) — 只使用一個 char 型別的累積變數,不需要任何額外空間。
Function findTheDifference(s, t):
result = 0
For each character c in s:
result = result XOR c // s 中的字符先 XOR 進來
For each character c in t:
result = result XOR c // t 中相同字符與 s 中的互相抵消
// 只有 t 中額外的那個字符沒有配對,留在 result 中
Return result (as char)字符計數法 O(n) 時間,O(1) 空間:建立大小為 26 的計數陣列,先對 s 所有字符計數加一,再對 t 所有字符計數減一,最後計數為 -1(或 1,取決於方向)的那個字符即為答案。空間上雖用了大小 26 的陣列,但屬於常數空間。
排序法 O(n log n) 時間,O(n) 空間:對 s 和 t 分別排序後逐位比較,第一個不同的位置即為答案(若全部相同則 t 末尾多的字符即是)。邏輯直觀但時間複雜度較高。
ASCII 求和法 O(n) 時間,O(1) 空間:計算 t 中所有字符 ASCII 值的總和減去 s 中所有字符 ASCII 值的總和,差值即為額外字符的 ASCII 值。與 XOR 法思路相似,但使用加減法;對於大型字串可能有整數溢出風險(可用 long long)。
t 比 s 多了兩個額外字符,XOR 法是否仍然有效?應如何修改(提示:參考 Single Number III 的分組思路)?t 是 s 的子集(t 比 s 少一個字符),演算法需要如何調整?