22.12.15 Today’s Leetcode

1143. Longest Common Subsequene (Medium, Fail)

Dynamic Programming을 이용하는 풀이. DP를 쓰지 않고 풀려다가, 많이 실패했다. 임의의 테스트케이스를 많이 만들어보는게 도움이 되었다. 해보다가 이 방식으로 구현이 안될것같다고 생각되면 다른 방식으로 생각해보는 습관을 길러야겠다.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # dp[i][j] means that length of longest common subsequence between text1[:i], text2[:j]
        m, n = len(text1), len(text2)
        dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
        for i in range(m):
            for j in range(n):
                if text1[i] == text2[j]:
                    # if text[i] and text2[j] are equal, dp[i + 1][j + 1] = 1 + dp[i][j]
                    dp[i + 1][j + 1] = 1 + dp[i][j]
                else:
                    # else
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]) 
        return dp[-1][-1]

# 처음 생각한 방식 
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        a, b = len(text1), len(text2)
        c, d = min(a, b), max(a, b)
        target = 0 if a > b else 1
        texts = [text1, text2]
        pos = [0, 0]
        res = 0
        while pos[target] < d and pos[target - 1] < c:
            c1, c2 = texts[target][pos[target]], texts[target - 1][pos[target - 1]]
            # 여기는 무슨 개짓거리?
            if c2 not in texts[target][pos[target]:]:
                pos[target - 1] += 1
            elif c1 == c2:
                res += 1
                pos[target] += 1
                pos[target - 1] += 1
            else:
                # 결국 이 부분을 해결하지 못해서 O(n)은 실패했다.
                # move longest text's index, why?
                pos[target] += 1
                    
        print(pos)
        print(res)
        # print(self.longestCommonSubsequence(text2, text1))
        return res

850. Rectangle Area Ⅱ (Hard, Fail)

Time Limit Exceeded. 생각나는 대로 구현했다. Combination을 이용하여 하나도 겹치지 않는 넓이에서 두 개의 사각형이 겹치는 넓이를 빼고, 세 개의 사각형이 겹치는 넓이를 더하고.. 이런식으로 반복하면 구할 수 있다고 생각했고 그대로 구현했지만, 다른 방식이 있는듯 하다. 위 문제와 마찬가지로 DP를 써야할것 같은데, 내일 생각해보기로 했다.

class Solution:

    def coord_overlap(self, t1, t2):
        #  t1 : 1         2
        #  t2 :              3         4
        if t1[1] < t2[0] or t1[0] > t2[1]:
            return[-1, -1]
        return [max(t1[0], t2[0]), min(t1[1], t2[1])]

    def overlap(self, rect1, rect2):
        x = self.coord_overlap([rect1[0], rect1[2]], [rect2[0], rect2[2]])
        y = self.coord_overlap([rect1[1], rect1[3]], [rect2[1], rect2[3]])
        # print(x, y)
        return (x[1] - x[0]) * (y[1] - y[0]) % (10**9 + 7), [x[0], y[0], x[1], y[1]]

    def overlap_comb(self, comb):
        overlapped = [0, 0, 10**9, 10**9]
        area = -1
        for rect in comb:
            area, overlapped = self.overlap(overlapped, rect)
        return area

    # we cannot use 2D array!
    # (4 + 3 + 2) no overlap
    # (2 + 1 + 1) 1 ovelap
    # (1) 2 overlap
    # 9 - 4 + 1 = 7
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        res = 0
        n = len(rectangles)
        types = 1
        for i in range(1, n + 1):
            combs = list(itertools.combinations(rectangles, i))
            for comb in combs:
                res += self.overlap_comb(comb) * types
        if res < 0:
            res += 10**9 + 7
        return res