LeetCode / Find the Difference

シンプルな問題ですが、dictionary使ったり、Counter使ったり、アスキーコード使ったり、ビット演算使ったりと、解法が多岐にわたる良問かも。

https://leetcode.com/problems/find-the-difference/

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

文字列sに対して、ランダムに組み換えた上で新たな文字を追加した文字列tがあり、追加された文字を特定する問題。

解答・解説

解法1

私の解法です。collections.Counterを使う方法。

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        count_s = collections.Counter(s)
        count_t = collections.Counter(t)
        for k in count_t:
            if count_t[k] != count_s[k]:
                return k

公式ドキュメントに記載の通り、カウンタオブジェクトは辞書のインタフェースを持ちますが、存在しない要素に対して KeyError を送出する代わりに 0 を返すという違いがあるので、if count_t[k] != count_s[k] とすれば、kがsに存在しない場合もcount_s[k] = 0が返り、if条件にひっかけることができます。

解法2

以下、Discussionから。 Counterを使わずdictionaryで解く方法。dic.get()でkeyがなくても処理できることをなかなか覚えられない。。

class Solution(object):
    def findTheDifference(self, s, t):
        dic = {}
        for ch in s:
            dic[ch] = dic.get(ch, 0) + 1
        for ch in t:
            if dic.get(ch, 0) == 0:
                return ch
            else:
                dic[ch] -= 1

解法3

アスキーコードを使って文字列を整数の和としてしまい、2つの文字列の差分をとって、最後に文字に戻す方法。

class Solution:
    def findTheDifference(self, s, t):
        diff = 0
        for i in range(len(s)):
            diff -= ord(s[i])
            diff += ord(t[i])
        diff += ord(t[-1])
        return chr(diff)

解法4

XOR(排他的論理和)を使う方法。

class Solution:
    def findTheDifference(self, s, t):
        code = 0
        for ch in s + t:
            code ^= ord(ch)
        return chr(code)

XORは和をとった2つの要素が同じであれば0になることを利用します。例えば、"aabbc"という文字列についてアスキーコードに変換してXORをとっていくと、以下のようになります。

for ch in "aabbc":
    code ^= ord(ch)
    print(ch, code)
# a 97
# a 0
# b 98
# b 0
# c 99

つまり、s, tの2つの文字列を結合してXORをとっていくと、文字列の差の分だけが残ることになります。