問題文

問題文はそのままコピーします。

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.

 

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"
Example 3:

Input: s = "a", t = "aa"
Output: "a"
Example 4:

Input: s = "ae", t = "aea"
Output: "a"
 

Constraints:

0 <= s.length <= 1000
t.length == s.length + 1
s and t consist of lower-case English letters.

Exampleのように、s = 'ae', t='aea'の時、このt配列のaをoutputしたいのことです。

簡単だと思いますが、ある特別な方法をシェアしたいと思っています。

解き方

この問題に対して、最初に思いついた方法はfor文でループして、dictを2つ使ってそれぞれ配列の要素をcountするだと思います。

だが！もっと面白い解き方があります！

pythonの組み込み関数のord()とchr()を使って、listのみで問題を解決できます！

では！コードを載ります。

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        if len(s) == 0:
            return t
        
        table = [0] * 26
        
        for i in range(len(t)):
            if i < len(s):
                table[ord(s[i]) - ord('a')] -= 1
            table[ord(t[i]) - ord('a')] += 1
        
        for i in range(26):
            if table[i] != 0:
                return chr(i + 97)
        return 'a'

1行目と2行目はleetcode上のコードなので、基本は無視しても大丈夫です。

最初はif文で、配列sがもしなにも入っていないなら、そのまま配列tが戻ります。

そして、if文が成り立っていない場合、26個の要素が含まれている配列を作成します。

続いて、for文はややこしいなので、図に合わせて説明します。

例えば、上の配列はs, 下は配列tとします。この2つの配列に対して、同時にfor文を掛けます。最初に出てきたのは配列sのaです。この時、countを-1にします。続いて、配列tの最初の要素はbで、countを+1にします。2回目に入って、配列sのbのcountを-1にし、配列tのcの countを+1にします。ここで、2つの配列にある要素bのcountを思い出してください！、-1, +1で0になります！。そのあとは同じのことを繰り返し、最後は必ずどっちかの要素が1になります。私たちはこの0ではない要素を探せばよいです。

って、ordとchrはなんやろと思うかもしれませんが、簡単です！indexを設定することです。

print(ord('a'))
>>> 97

文字列aを数値に変化することです。一方、chrは数値を文字列に変換することです。

ord(s[i]) - ord('a')こうやって書く理由として、私たち先作った26個要素が含まれている配列があるではないですか。ordで変換すると26を超えてしまったので、ようするにindex 0,1,2,3,4...を作るためです。

これでfor文は終了し、最後はcount != 0の要素を探せてreturnしたら良いです。

参考

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