23.02.01 Today’s leetcode

1071. Greatest Common Divisor of Strings (easy)

유클리드 호제법을 이용한 풀이. String divide를 구현하는데 힘들었지만, 가능하긴 했다.

class Solution:

    def divide(self, str1, str2):
        n = len(str2)
        temp = str1[:]
        while temp[:n] == str2:
            temp = temp[n:]

        while temp[len(temp) - n:] == str2:
            temp = temp[:len(temp) - n]

        if temp == str1:
            return "a" # cannot divide
        return temp

    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if len(str1) < len(str2):
            str1, str2 = str2, str1
        # print(str1, str2)
        if str2 == "": return str1
        else:
            # num1 % num2
            temp = self.divide(str1, str2)
            if temp == "a": # cannot divide
                return ""
            return self.gcdOfStrings(str2, temp)
        

다른 정석적인 풀이. 기본적인 방향으로.

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        for i in range(min(len(str1), len(str2)), 0, -1):
            if (len(str1) % i) == 0 and (len(str2) % i) == 0:
                if str1[: i] * (len(str1) // i) == str1 and str1[: i] * (len(str2) // i) == str2:
                    return str1[:i]
        return ''

145. Binary Tree Postorder Traversal (easy)

class Solution:

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if root == None:
            return res
        res += self.postorderTraversal(root.left)
        res += self.postorderTraversal(root.right)
        res.append(root.val)
        return res

128. Longest Consecutive Sequence (medium)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        temp = collections.Counter()
        res = 0
        for n in nums:
            if temp[n] == 0:
                a, b = temp[n - 1], temp[n + 1]
                temp[n] = 1 + a + b
                # 이 부분이 잘 이해가 안된다.
                temp[n - a] = temp[n]
                temp[n + b] = temp[n]
                res = max(res, temp[n])

        return res