23.02.04 Today’s Leetcode

567. Permutation in String (medium)

Counter을 이용한 풀이.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        
        n1, n2 = len(s1), len(s2)
        if n1 > n2:
            return False

        target = collections.Counter(s1)
        counter = collections.Counter(s2[:n1])
        if target == counter:
            return True
        for i in range(n1, n2):
            a, b = s2[i], s2[i - n1]
            counter[a] += 1
            counter[b] -= 1
            if counter == target:
                return True
        return False

89. Gray Code (medium)

class Solution:
    def grayCode(self, n: int) -> List[int]:
        dp = [[] for x in range(n + 1)]
        dp[1] = [0, 1]
        def dfs(n):
            if len(dp[n]) > 0:
                return dp[n]
            a = self.grayCode(n - 1)
            b = [x + (2 ** (n - 1)) for x in a]
            b.reverse()
            res = a + b
            dp[n] = res
            return res
        return dfs(n)