Leetcode - Episode 1 - Three Easys

January 01, 2019 in Algorithms

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.

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

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

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


Comments or questions? I enjoy talking with readers over email.

Email newsletter 📧

I write about code. Get my posts, projects, and personal updates straight to your inbox!