This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Solution Notebook

Problem: Find the Difference.

See the LeetCode problem page.

Constraints

  • Can we assume the strings are ASCII?
    • Yes
  • Is case important?
    • The strings are lower case
  • Can we assume the inputs are valid?
    • No, check for None
  • Can we assume this fits memory?
    • Yes

Test Cases

  • None input -> TypeError
  • 'aaabbcdd', 'abdbacade' -> 'e'

Algorithm

  • Keep a dictionary of seen values in s
  • Loop through t, decrementing the seen values
    • If the char is not there or if the decrement results in a negative value, return the char

Complexity:

  • Time: O(m+n), where m and n are the lengths of s, t
  • Space: O(h), for the dict, where h is the unique chars in s

Code

In [1]:
class Solution(object):

    def find_diff(self, s, t):
        if s is None or t is None:
            raise TypeError('s or t cannot be None')
        seen = {}
        for char in s:
            if char in seen:
                seen[char] += 1
            else:
                seen[char] = 1
        for char in t:
            try:
                seen[char] -= 1
            except KeyError:
                return char
            if seen[char] < 0:
                return char
        return None

Unit Test

In [2]:
%%writefile test_str_diff.py
import unittest


class TestFindDiff(unittest.TestCase):

    def test_find_diff(self):
        solution = Solution()
        self.assertRaises(TypeError, solution.find_diff, None)
        self.assertEqual(solution.find_diff('aaabbcdd', 'abdbacade'), 'e')
        print('Success: test_find_diff')


def main():
    test = TestFindDiff()
    test.test_find_diff()


if __name__ == '__main__':
    main()
Overwriting test_str_diff.py
In [3]:
%run -i test_str_diff.py
Success: test_find_diff