Leetcode - Episode 1 - Three Easys

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.

  1. Jewels and Stones

Problem: Given a string J of unique characters, how many unique characters from this string are present in string S.

class Solution:
def numJewelsInStones(self, J, S):
:type J: str
:type S: str
:rtype: int
jewels = set()
for i in J:
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.

  1. Unique Email Addresses

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('@')[0].split('+')[0].replace('.', '')
# concat with the domain name
domain = email.split('@')[1]
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.

  1. To Lower Case

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)
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.