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.

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

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

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