Find the Difference Python

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.
Using sorting
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        x = sorted(s)
        y = sorted(t)
        i = 0
        while i < len(x):
            if x[i] != y[i]:
                return y[i]
            i+=1
        return y[i]
Time Complexity : O(nlogn)
Space Complexity : O(1) sorting in python takes inplace so O(1)
Using Hashmap :
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        counter_s = Counter(s)
        for ch in t:
            if ch not in counter_s or counter_s[ch] == 0:
                return ch
            else:
                counter_s[ch] -=1
Time Complexity : O(n)
Space Complexity : O(1)
Using Bit manipulation :
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        res = 0
        for i in s:
            res ^= ord(i)
            
        for i in t:
            res ^= ord(i)
            
        return chr(res)
Time Complexity : O(n)
Space complexity : O(1)

No comments:

Post a Comment

Featured Post

H1B Visa Stamping at US Consulate

  H1B Visa Stamping at US Consulate If you are outside of the US, you need to apply for US Visa at a US Consulate or a US Embassy and get H1...