23.04.23 Today’s Leetcode

1416. Restore The Array (hard)

DP with memoization : TLE at 70/83

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:

        n = len(s)
        dp = [0] * n
        MOD = 10**9 + 7 
        
        @lru_cache(None)
        def dfs(index=0):
            if index >= n:
                return 1
            if dp[index] > 0:
                return dp[index]
            temp = 0
            for i in range(index + 1, n + 1):
                num = int(s[index:i])
                if num == 0:
                    break
                if num >= 1 and num <= k:
                    temp += dfs(i)
            
            dp[index] = temp
            return temp
    
        return dfs(0) % MOD

DP with TOP-Down

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[-1] = 1
        
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                continue
            num = 0
            j = i
            while j < n and int(s[i:j + 1]) <= k:
                num += dp[j + 1]
                j += 1
            dp[i] = num % (10 ** 9 + 7)
        
        return dp[0]

1977. Number of Ways to Separate Numbers (hard)

DP는 어렵다.

class Solution:
    def numberOfCombinations(self, num: str) -> int:
        n = len(num)
        dp = [[0 for i in range(n)] for j in range(n)]
        for s in range(n - 1, -1, -1):
            for i in range(s + 1, n):
                dp[s][i] = dp[s][i - 1]
                pLen = i - s
                if(num[i] == '0' or i + pLen > n):           
                    continue
                if(num[s : i] <= num[i : i + pLen]):   
                    dp[s][i] += 1 if i + pLen == n else dp[i][i + pLen] - dp[i][i + pLen - 1]
                if(i + pLen < n):
                    dp[s][i] += 1
                    dp[s][i] += dp[i][n - 1] -  dp[i][i + pLen]
        return (dp[0][-1] + 1) % (10 ** 9 + 7) if num[0] != '0' else 0

392. Is Subsequence (easy)

오랜만에 쉬운 문제를 푸니, 마음이 편해진다..

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        j = 0
        m, n = len(s), len(t)
        for i in range(m):
            while j < n and t[j] != s[i]:
                j += 1
            if j == n or t[j] != s[i]:
                return False
            j += 1
        return True