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