LeetCode 389. Find the Difference (Python3)
はじめに
LeetCode 「389. Find the Difference」の問題を Python3 で解きました。
問題
問題文
You are given two strings s and t.
String t is generated by random shuffling string s and then add one more letter at a random position.
Return the letter that was added to t.
和訳
2つの文字列 s と t が与えられます。
文字列 t は、文字列 s をランダムにシャッフルし、ランダムな位置に文字を1つ追加することで生成されます。
t に追加された文字を返します。
例
Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.
Input: s = "", t = "y"
Output: "y"
制約
- 0 <= s.length <= 1000
- t.length == s.length + 1
- s and t consist of lowercase English letters.
解答1(Counter)
まずはcollections.Counterを使用する方法です。
sに含まれる文字の出現回数をCounterで数えて、tに含まれる文字の中から対応するカウントを減らし、カウントが0の文字が出たらreturnします。
Counterは存在しないキーにアクセスしても KeyError ではなく 0 を返すため、
counter[ch] == 0 で「まだ登場していない新しい文字」を検出できます。
コード
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
counter = collections.Counter(s)
for ch in t:
if counter[ch] == 0:
return ch
counter[ch] -= 1
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(k)
- 英小文字26文字しかないので実質O(1)
解答2(count)
文字列のcount()メソッドで文字の出現回数をカウントすることができるので、以下のような解答もできます。
コード
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
for ch in t:
if t.count(ch) > s.count(ch):
return ch
計算量
- 時間的計算量：O(n²)
- 空間的計算量：O(1)
解答3(ord)
ord()メソッドは、Unicode文字に対しその文字の文字コードを表す整数を返します。
sとtのそれぞれの文字の文字コードの合計を比較し、その差分が追加され文字コードとなります。
chr()で文字コードから文字列に変換できます。
コード
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
return chr(sum(map(ord, t)) - sum(map(ord, s)))
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(1)
解答4(XOR)
ビット演算でXOR（^）を使用して解くことも可能です。
XOR（^）は次の性質があります。
a ^ a = 0: 同じ値をXORすると0になる
文字列sとtの文字を全てXORすると、もともとsにあった文字はtとのペアで打ち消しあい、最終的に追加された文字だけが残ります。
コード
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
res = 0
for ch in s + t:
res ^= ord(ch)
return chr(res)
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(1)
Discussion