This series involves tackling Leetcode problems and discussing my solutions with an aim to improve at problem solving and algorithmic analysis. For most problems, I will be aiming for the most optimal solution. I’ve recently been reviewing some academic content on algorithms and data-structures.
Problem: Given a string
J of unique characters, how many unique characters from this string are present in string
class Solution: def numJewelsInStones(self, J, S): """ :type J: str :type S: str :rtype: int """ jewels = set() for i in J: jewels.add(i) stones = 0 for i in S: if i in jewels: stones += 1 return stones
My solution achieves a runtime complexity of
O(n + m) - this is the minimum possible because both strings must be iterated through at least once – and ‘searching’ a Set is
O(1). The space complexity is
O(n) as one Set was required to store the characters we are looking for.
After reading the discussion board, I saw that this code can be improved by using Python’s collections.Counter
Counter objects - A counter tool is provided to support convenient and rapid tallies.
Problem: Given a list
E of emails, return the number of distinct emails.
You may want to check the full problem statement for the specific email rules.
class Solution: def numUniqueEmails(self, emails): """ :type emails: List[str] :rtype: int """ distinct = set() for email in emails: # get the local name local = email.split('@').split('+').replace('.', '') # concat with the domain name domain = email.split('@') distinct.add(local + domain) return len(distinct)
My solution is not optimized for speed but solves the problem with a reasonably clean style. After reviewing the discussion posts, I saw that a quick optimization would be to cache both sides of the
@ symbol at the same time by using
local, domain = email.split('@').
To be fully optimal, I presume that a careful manual loop would be required.
Problem: implement ToLowerCase() (presumably without standard library functions!)
class Solution: def toLowerCase(self, str): """ :type str: str :rtype: str """ lowered =  for i in str: char_code = ord(i) # if A-Z if char_code < 91 and char_code > 64: lowered += chr(char_code + 32) else: lowered += i return ''.join(lowered)
My solution has a runtime complexity of
O(n) with a space complexity of
O(n). Depending on the underlaying implementation, it may be quicker to use a Dictionary of uppercase to lowercase characters for the conversion.