LeetCode 풀기 - 389. Find the Difference

389. Find the Difference

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

Find the Difference - LeetCode

문제)

솔루션1) HashMap

각각의 해쉬맵 구성.

원래 문자의 hashmap에서 random 생성된 문자 해쉬맵을 하나씩 제거해나가서 최종적으로 남은 것이 추가된 문자가됩니다.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        s = Counter(s)
        t = Counter(t)
        for ch, freq in s.items():
            if ch in t:
                t[ch] -= freq
                if t[ch] == 0:
                    del t[ch]
        
        return list(t.keys())[0]

솔루션2) XOR

XOR은 교환법칙, 결합 법칙 성립.

 

xor 특징:

- A^0 = A

- A^A = 0

 

결국, s와 t의 각 문자에 대해서 xor을 취하면 추가된 한 문자만 남게됩니다.

 

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        res = 0
        for c in s+t:
            res ^= ord(c)
        return chr(res)