一魚多吃 用XOR性質來解 字串的差異Find the Difference Leetcode #389

這題的題目在這裡

題目給定兩個字串s和t，t是s隨機打散後的字串，並且在t裡面額外多加了一個字元，要求我們找出額外多加入的那個字元。

Example 1:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:

Input: s = "", t = "y"
Output: "y"

約束條件:

Constraints:

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s and t consist of lowercase English letters.(只會有小寫英文字母)

演算法:

除了傳統字典去記錄出現次數的方法以外，

其實，也可以用到前面在Single Number學過的技巧，用XOR self-inverse的特質，來消去成雙成對的元素。

Self-inverse :

A ⊕ A = 0

題目已經說t 和 s 是重新隨機打散過的排列，只額外多加入了一個字元。

令我們所求的字元為target。也就是說，除了target以外的字元，都成雙成對出現，一次出現在s，一次出現在t。

全部用迴圈掃描一遍，同時滾動計算XOR的值，最後留下來的剛好就會是我們的所求target，也就是額外多加入的那一個字元。

程式碼:

class Solution:
　def findTheDifference(self, s: str, t: str) -> str:

　　# Each character appear twice, one in s, the other in t.
　　# The extra one only shows up once in t.

　　letter = 0
　　for char in s:
　　　letter ^= ord(char)
　　
　　for char in t:
　　　letter ^= ord(char)
　　　
　　return chr(letter)

時間複雜度:

O( m+n ) 用線性掃描分別掃描兩個字串，s和t。

空間複雜度:

O(1) 只用了固定尺寸的臨時變數，所佔用空間為常數級別，為O(1)

最後學完這題，記得去複習 Single Number 這一題，兩者用到的都是同一個很實用的XOR運算子的性質 Self inverse A ⊕ A = 0

Reference:

[1] LeetCode - The World's Leading Online Programming Learning Platform