389.Find the Difference

Tags: [map], [math]

Link: https://leetcode.com/problems/find-the-difference/?tab=Description

Given two stringssandtwhich consist of only lowercase letters.

Stringtis generated by random shuffling stringsand then add one more letter at a random position.

Find the letter that was added int.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

Solution: math

class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        if not s:
            return t
        if not t:
            raise ValueError('the input is invalid')

        s_char_code_sum = sum([ord(c) for c in s])
        t_char_code_sum = sum([ord(c) for c in t])
        return chr(t_char_code_sum - s_char_code_sum)

Revelation:

• Think we have an arr1 = [100, 200, 300], and arr2 = [300, 200, 1000, 100], then we know there is only one more extra element in arr2, all other elements of arr2 all come from arr1, now we want to find the difference between arr1 and arr2. So we can sum all numbers in arr1 called sum1, and then sum all elements in arr2 called sum2, so the difference = sum2 - sum1. We can convert the char to char code, and apply the same approach on this question.

Note:

• Time complexity = O(max(s_len, t_len)), s_len is the length of the string s, and t_len is the length of the string t.

Solution: map

class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        if not s:
            return t
        if not t:
            raise ValueError('the input is invalid')

        s_c_map = {}
        for c in s:
            if c in s_c_map:
                s_c_map[c] += 1
            else:
                s_c_map[c] = 1

        for c in t:
            if c not in s_c_map or not s_c_map[c]:
                return c

            s_c_map[c] -= 1

        return None

Revelation:

• The meaning of this question is that: Given one string s, and shuffle the chars of s to build t, but add an extra char to t, write an algorithm to find this extra char.

Note:

• Time complexity = O(max(s_len, t_len)), s_len is the length of the string s, and t_len is the length of the string t.