23.01.02 Today’s Leetcode

520. Detect Capital (easy)

class Solution:
    def detectCapitalUse(self, word: str) -> bool:
        first = word[0].isupper()
        n = len(word)
        if first:
            for i in range(1, n - 1):
                a, b = word[i].isupper(), word[i + 1].isupper()
                if a != b:
                    return False
        else:
            for i in range(1, n):
                if word[i].isupper():
                    return False
        return True
        

141. Linked List Cycle (easy)

신기한점을 발견했다. list를 이용할 때와 set을 이용할 때의 차이가 엄청나게 많이 난다. 확실히 set에서는 index를 유지하지 않아서 그런지 속도면에서 list보다 훨씬 빨랐다.

# set 사용, 61ms
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        target = head
        nodes = set()
        while target:
            target = target.next
            if target in nodes:
                return True
            nodes.add(target)
        return False

# list 사용, 1466ms
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        target = head
        nodes = []
        while target:
            target = target.next
            if target in nodes:
                return True
            nodes.append(target)
        return False

131. Palindrome Partitioning (medium)

class Solution:
    def is_palindrome(self, s: str):
        return s == s[::-1]

    def dfs(self, s: str, res, current):
        n = len(s)
        if n == 0:
            res.append(current)
            return
        for i in range(1, n + 1):
            target = s[:i]
            if self.is_palindrome(target):
                temp = current[:]
                temp.append(target)
                self.dfs(s[i:], res, temp)

    def partition(self, s: str) -> List[List[str]]:
        res = []
        self.dfs(s, res, [])
        return res

132. Palindrome Partitioning II (hard)

처음 구현한 방식, 위에서 했던 것 처럼 재귀적으로 구현하려고 했으나, 막히는 부분이 있었음. 중간에 앞쪽의 pailndrome보다 뒤쪽의 palindrome이 더 긴 경우라던지, 아주 긴 문자열의 경우 제대로 값이 나오지 않았음.

class Solution:
    def is_palindrome(self, s: str):
        return s == s[::-1]

    def dfs(self, s: str):
        n = len(s)
        if n <= 1:
            return 0
        if self.is_palindrome(s):
            return 0
        for i in range(n, 0, -1):
            target = s[:i]
            if self.is_palindrome(target):
                # current.append(target)
                return self.dfs(s[i:]) + 1

    def minCut(self, s: str) -> int:
        return min(self.dfs(s), self.dfs(s[::-1]))

이건 최단시간 solution인데, dp를 이용해서 palindrome을 확장시켜나가면서 cut을 계산하는 방식인듯함.

class Solution:
    def minCut(self, s: str) -> int:
         # acceleration
        if s == s[::-1]: return 0
        
        # 한번에 쪼개지는지 체크
        for i in range(1, len(s)):
            if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                return 1
                
        # algorithm
        cut = [x for x in range(-1,len(s))]  # cut numbers in worst case (no palindrome)
        
        for i in range(len(s)):
            r1, r2 = 0, 0
            # use i as origin, and gradually enlarge radius if a palindrome exists
            # odd palindrome
            while i - r1 >= 0 and i + r1 < len(s) and s[i - r1] == s[i + r1]:
                cut[i + r1 + 1] = min(cut[i + r1 + 1], cut[i - r1] + 1)
                r1 += 1
            # even palindrome
            while i - r2 >= 0 and i + r2 + 1 < len(s) and s[i - r2] == s[i + r2 + 1]:
                cut[i + r2 + 2] = min(cut[i + r2 + 2], cut[i - r2] + 1)
                r2 += 1
        return cut[-1]