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 = 0for i in S:if i in jewels:stones += 1return 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 namelocal = email.split('@').split('+').replace('.', '')# concat with the domain namedomain = 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-Zif char_code < 91 and char_code > 64:lowered += chr(char_code + 32)else:lowered += ireturn ''.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.