Latest Posts

LeetCode: Generate Parentheses

12 September 2022

Generate Parentheses (Difficulty: Medium)

While this is a simple recursive solution, I would like to emphasize that we can use yield in Python to return multiple values with lazy manner. I believe this would be useful when a function is returning many values during its recursion.

class Solution:
    def recursive_gen(self, current, opened, closed, n):
        if opened == n and closed == n:
            yield current
        else:
            if opened > closed:  # can close the parentheses
                yield from self.recursive_gen(current + ')', opened, closed + 1, n)
            if opened + 1 <= n:
                yield from self.recursive_gen(current + '(', opened + 1, closed, n)
        
    def generateParenthesis(self, n: int) -> List[str]:
        return list(self.recursive_gen('', 0, 0, n))

LeetCode: Roman to Integer

03 September 2022

Roman to Integer (Difficulty: Easy)

This is an easy question. However, the important takeaway is that slicing string s = s[2:] is much slower than index manipulating
This is because left parts of string need to be taken down by garbage collection. Otherwise, it will cause memory leak.

class Solution:
    def romanToInt(self, s: str) -> int:
        symbol_value = {
            "I": 1, "IV": 4, "V": 5, "IX": 9,
            "X": 10, "XL": 40, "L": 50, "XC": 90,
            "C": 100, "CD": 400, "D": 500, "CM": 900,
            "M": 1000
        }
        
        num = 0
        i = 0
        while i < len(s):
            c2 = s[i:i+2]
            if c2 in symbol_value:
                num += symbol_value[c2]
                i += 2
                # s = s[2:]  this operation is slower than index-based method
                # b/c this requires memory operations such as garbage collection
            else:
                c1 = s[i]
                num += symbol_value[c1]
                i += 1
                # s = s[1:]  
        
        return num

LeetCode: Longest Substring Without Repeating Characters

23 August 2022

Longest Substring Without Repeating Characters (Difficulty: Medium)

class Solution:
    @staticmethod
    def delete_substr(substr, i):
        del_keys = []
        for key in substr:
            if substr[key] < i:
                del_keys += [key]
        for key in del_keys:
            substr.pop(key)
                
    def lengthOfLongestSubstring(self, s: str) -> int:
        substr = {}
        x = []  # x[i] = length of longest substr having s[i]
        for i in range(len(s)):
            c = s[i]
            if c in substr:
                self.delete_substr(substr, substr[c])
            substr[c] = i
            # print(substr)
            x += [len(substr)]
        
        if len(x) ==0:
            return 0
        
        return max(x)

LeetCode: Split Array Into Consecutive Subsequences

19 August 2022

Split Array Into Consecutive Subsequences (Difficulty: Medium)

Will be back to write things up

class Solution:
    @staticmethod
    def check_appendable(list_subseq, n):
        i = 0
        while i < len(list_subseq):
            subseq = list_subseq[i]
            if subseq[-1] + 1 < n:
                if len(subseq) < 3:  # return false as answer
                    return "falseisanswer"
                list_subseq.pop(i)
                continue
                    
            if subseq[-1] + 1 == n:
                return i
            i += 1
            
        return None
        
    def isPossible(self, nums: List[int]) -> bool:
        list_subseq = []
        
        for n in nums:
            idx = self.check_appendable(list_subseq, n)
            if idx == "falseisanswer":
                return False
            elif idx != None:
                list_subseq[idx] += [n]
            else:
                list_subseq = [[n]] + list_subseq
        
        for subseq in list_subseq:
            if len(subseq) < 3:
                return False
            
        return True

LeetCode: Add Two Numbers

18 August 2022

Add Two Numbers (Difficulty: Medium)

쉬운 문제라고 생각했는데 Linked List 예외처리가 의외로 경우의 수가 많았다. 주어진 l1과 l2의 길이가 다를 수 있다는 것이 포인트.
- l1 또는 l2가 하나만 값이 있는 경우
- 두개 모두 값이 없는 경우
- 두개 모두 값이 있는 경우
  그리고 위에 더해서 밑 자리수에서 carry가 발생하는 경우까지 합하면 총 8가지의 경우의 수가 발생한다.

값이 없는 경우 l1.next를 참조하면 오류가 나니 if문으로 처리해주어야 한다.

아래 코드의 시간복잡도는 O(N)

l1과 l2의 길이의 차가 크다면 중간에 next를 긴 쪽으로 연결시켜 버리면 약간의 성능향상이 있을 듯하다. 하지만 Big-O는 최악의 경우를 상정하므로 변화는 없다.

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

        
class Solution:
    def get_val(self, node):
        if node:
            return node.val
        else:
            return 0
        
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        base_node = ListNode()
        prev_node = base_node
        overflow = 0
        
        while not(l1 == None and l2 == None and overflow == 0):
            new_sum = self.get_val(l1) + self.get_val(l2) + overflow
            overflow = new_sum // 10
            new_sum -= overflow * 10
            
            new_node = ListNode(new_sum)
            prev_node.next = new_node
            prev_node = new_node
            
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        
        return base_node.next