Leetcode 1416:恢复数组(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1416:恢复数组(超详细的解法!!!)

in leetcode with 0 comment

某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串,我们所知道的信息只有:数组中所有整数都在 [1, k] 之间,且数组中的数字都没有前导 0 。

给你字符串 s 和整数 k 。可能会有多种不同的数组恢复结果。

按照上述程序,请你返回所有可能输出字符串 s 的数组方案数。

由于数组方案数可能会很大,请你返回它对 10^9 + 7 取余 后的结果。

示例 1:

输入:s = "1000", k = 10000
输出:1
解释:唯一一种可能的数组方案是 [1000]

示例 2:

输入:s = "1000", k = 10
输出:0
解释:不存在任何数组方案满足所有整数都 >= 1 且 <= 10 同时输出结果为 s 。

示例 3:

输入:s = "1317", k = 2000
输出:8
解释:可行的数组方案为 [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]

示例 4:

输入:s = "2020", k = 30
输出:1
解释:唯一可能的数组方案是 [20,20] 。 [2020] 不是可行的数组方案,原因是 2020 > 30 。 [2,020] 也不是可行的数组方案,因为 020 含有前导 0 。

示例 5:

输入:s = "1234567890", k = 90
输出:34

提示:

解题思路

首先比较容易想到递归记忆化的思路,定义函数$f(i)$表示$s[i:]$的可行方案数,那么

接着考虑边界问题,如果i=len(s)表示遍历结束有可行解;如果当前的字符是'0',那么必然无解。

sys.setrecursionlimit(1000000)
from functools import lru_cache
class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        mod, n = 10**9 + 7, len(s)

        @lru_cache(None)
        def dfs(cur):
            if cur == n: return 1
            if s[cur] == '0': return 0
            res = 0
            
            for i in range(cur + 1, n + 1):
                if 1 <= int(s[cur: i]) <= k:
                    res = (res + dfs(i)) % mod
                else:
                    break
            return res
        return dfs(0)

也可以将上面这个代码写成动态规划形式。

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        n, mod = len(s), 1000000007
        dp = [0] * (n + 1)
        dp[-1] = 1
        
        for i in range(n - 1, -1, -1):
            if s[i] == '0': continue
            cur = 0
            for t in range(1, n - i + 1):
                cur = cur * 10 + ord(s[i + t - 1]) - 48
                if cur > k: break
                dp[i] = (dp[i] + dp[i + t]) % mod
        return dp[0]

可以注意到上面计算的过程中t一定是小于len(str(k))的,所以空间复杂度还可以进一步优化。

reference:

https://leetcode.com/problems/restore-the-array/discuss/585597/C%2B%2BJava%3A-3-Approaches

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses