Teaching Kids Programming – Find the Difference of Two Almost Same Strings


Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Find the Difference of Two Almost Same Strings

If we sort both strings, and check character by character, the first difference is the one we are looking for or the difference must be the last character of sorted t (time complexity O(NLogN) – space O(1))

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        s = sorted(s)
        t = sorted(t)
        i = 0
        while i < len(s):
            if s[i] != t[i]:
                return t[i]
            i += 1
        return t[-1]
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        s = sorted(s)
        t = sorted(t)
        i = 0
        while i < len(s):
            if s[i] != t[i]:
                return t[i]
            i += 1
        return t[-1]

Given there are only 1 difference, if we XOR all characters, the difference must be the result or XOR – time complexity O(N) – space complexity O(1):

1
2
3
4
5
6
7
8
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        ans = 0
        for i in s:
            ans ^= ord(i)
        for i in t:
            ans ^= ord(i)
        return chr(ans)
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        ans = 0
        for i in s:
            ans ^= ord(i)
        for i in t:
            ans ^= ord(i)
        return chr(ans)

Improved to one loop:

1
2
3
4
5
6
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        ans = 0
        for i in s + t:
            ans ^= ord(i)
        return chr(ans)
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        ans = 0
        for i in s + t:
            ans ^= ord(i)
        return chr(ans)

We can use two Counter object and check them accordingly – time and space complexity is O(N), two hash maps.

1
2
3
4
5
6
7
8
9
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        cs = Counter(s)
        ct = Counter(t)
        for i in ct:
            if i not in cs:
                return i
            if cs[i] != ct[i]:
                return i            
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        cs = Counter(s)
        ct = Counter(t)
        for i in ct:
            if i not in cs:
                return i
            if cs[i] != ct[i]:
                return i            

We can also use only one hash map, and then decrement the seen character – time and space complexity is O(N) – however only 1 hash map.

1
2
3
4
5
6
7
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        cs = Counter(s)
        for i in t:
            if i not in cs or cs[i] == 0:
                return i
            cs[i] -= 1
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        cs = Counter(s)
        for i in t:
            if i not in cs or cs[i] == 0:
                return i
            cs[i] -= 1

See also: C/C++ Find the Difference of Two Lowercase Strings

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
596 words
Last Post: C Program to Time Command using clock_gettime
Next Post: BASH Function to Check if sudo Available

The Permanent URL is: Teaching Kids Programming – Find the Difference of Two Almost Same Strings

Leave a Reply