389. Find the Difference

Description

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”

Constraints:

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s and t consist of lowercase English letters.

Submitted Code

class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        t_count = {}

        for ch in t:
            t_count[ch] = t_count.get(ch, 0) + 1
        
        for ch in s:
            if ch in t_count:
                t_count[ch] -= 1

            if t_count[ch] == 0:
                del t_count[ch]

        return [k for k, v in t_count.items() if v == 1][0]

Runtime: ** ms | Beats **66.49%
Memory: 12.41 MB | Beats 56.93%

해시 테이블을 이용하면 마지막에 {'e': 1} 처럼 t에 추가된 문자 하나만 남게 된다.

Other Solutions

1st

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        c = 0
        for cs in s: c ^= ord(cs) #ord is ASCII value
        for ct in t: c ^= ord(ct)
        return chr(c) #chr = convert ASCII into character

time complexity: 𝑂(𝑛)
space complexity: 𝑂(1)

XOR 연산의 성질(같은 값끼리는 상쇄되어서 0이 되고, 0은 아무 영향이 없고, 연산 순서와 무관)을 이용할 수 있다. ord()로 문자를 정수로 변환한 후, 모든 숫자를 XOR로 처리하면 마지막에 t에만 존재하는 문자만 결과로 남는다.

2nd

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        s_sum = sum(ord(x) for x in s)
        t_sum = sum(ord(y) for y in t)
    
        return chr(t_sum - s_sum)

XOR 연산 없이 아스키코드 값을 모두 더한 후 서로 빼는 것으로도 해결할 수 있다.

3rd

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        for c in t:
            if t.count(c) > s.count(c):
                return(c)

t에서 카운트 한 c의 갯수가 s에서 카운트한 갯수보다 많다면 c는 t에만 있다는 것이 되기 때문에 쉽게 찾을 수 있다.