跳转至

1416. 恢复数组

来源第 24 场双周赛 Q4难度困难分数1919

题目描述

某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [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

 

提示：

  • 1 <= s.length <= 10^5.
  • s 只包含数字且不包含前导 0 。
  • 1 <= k <= 10^9.

解法

方法一

思考

将数字串切成若干属于 \([1,k]\) 且无前导零的整数， \(n\le 10^5\)，枚举所有切法不可行。 \(k\le 10^9\)，从某一位置向后延伸的合法数字长度不超过 \(10\)。

定义 \(f(i)\) 为后缀 \(s[i:]\) 的恢复方案数：若 \(s[i]='0'\) 则无法开始；否则枚举结束位置 \(j\)，在数值 \(\le k\) 时累加 \(f(j+1)\)。对 \(f(i)\) 记忆化或改写成从右向左的线性 DP。

从右往左计算 \(f(i)\)， \(f(n)=1\)。 \(s[i]='0'\) 时 \(f(i)=0\)；否则从下标 \(i\) 起向右拼数，数值一旦大于 \(k\) 就停止，并把每个合法切点后的 \(f(j+1)\) 累加进 \(f(i)\)。答案是 \(f(0)\)，对 \(10^9+7\) 取模。

时间复杂度 \(O(nd)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是 \(s\) 的长度， \(d\) 是 \(k\) 的十进制位数，不超过 \(10\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        mod = 10**9 + 7
        n = len(s)
        f = [0] * (n + 1)
        f[n] = 1
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                continue
            x = 0
            for j in range(i, n):
                x = x * 10 + int(s[j])
                if x > k:
                    break
                f[i] = (f[i] + f[j + 1]) % mod
        return f[0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int numberOfArrays(String s, int k) {
        final int mod = 1_000_000_007;
        int n = s.length();
        int[] f = new int[n + 1];
        f[n] = 1;
        for (int i = n - 1; i >= 0; --i) {
            if (s.charAt(i) == '0') {
                continue;
            }
            long x = 0;
            for (int j = i; j < n; ++j) {
                x = x * 10 + s.charAt(j) - '0';
                if (x > k) {
                    break;
                }
                f[i] = (int) ((f[i] + f[j + 1]) % mod);
            }
        }
        return f[0];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int numberOfArrays(string s, int k) {
        const int mod = 1e9 + 7;
        int n = s.size();
        vector<int> f(n + 1);
        f[n] = 1;
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == '0') {
                continue;
            }
            long long x = 0;
            for (int j = i; j < n; ++j) {
                x = x * 10 + s[j] - '0';
                if (x > k) {
                    break;
                }
                f[i] = (f[i] + f[j + 1]) % mod;
            }
        }
        return f[0];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func numberOfArrays(s string, k int) int {
    const mod = int(1e9 + 7)
    n := len(s)
    f := make([]int, n+1)
    f[n] = 1
    for i := n - 1; i >= 0; i-- {
        if s[i] == '0' {
            continue
        }
        x := 0
        for j := i; j < n; j++ {
            x = x*10 + int(s[j]-'0')
            if x > k {
                break
            }
            f[i] = (f[i] + f[j+1]) % mod
        }
    }
    return f[0]
}

方法二：环形数组优化空间

思考

方法一为每个后缀都保存一个状态，但从某个位置开始的数字最多只有 \(d\) 位，其中 \(d\) 是 \(k\) 的十进制位数。我们从右向左计算时，当前状态只会读取后面 \(d\) 个后缀的答案。因此可以用长度为 \(d+1\) 的环形数组保留这些状态：当前位置对应的槽位不会覆盖接下来还要读取的值。转移保持不变，空间不再随字符串长度增长。

设 \(f(i)\) 为后缀 \(s[i:]\) 的合法拆分数，初始 \(f(n)=1\)。若 \(s[i]\) 为 0，则 \(f(i)=0\)；否则从位置 \(i\) 起取至多 \(d\) 位，只要数值不超过 \(k\)，就把对应的 \(f(j+1)\) 加入答案，并对 \(10^9+7\) 取模。

把 \(f(i)\) 存在下标 \(i \bmod (d+1)\)。计算它时只读取下标在 \([i+1,i+d]\) 的状态，这些状态都不会占用 \(i\) 的槽位。时间复杂度与方法一相同，为 \(O(nd)\)；辅助空间从 \(O(n)\) 降为 \(O(d)\)，且这里 \(d\le 10\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        mod = 10**9 + 7
        n = len(s)
        d = len(str(k))
        f = [0] * (d + 1)
        f[n % (d + 1)] = 1
        for i in range(n - 1, -1, -1):
            ways = 0
            if s[i] != '0':
                value = 0
                for j in range(i, min(n, i + d)):
                    value = value * 10 + int(s[j])
                    if value > k:
                        break
                    ways = (ways + f[(j + 1) % (d + 1)]) % mod
            f[i % (d + 1)] = ways
        return f[0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int numberOfArrays(string s, int k) {
        constexpr int mod = 1e9 + 7;
        int n = s.size(), d = to_string(k).size();
        vector<int> f(d + 1);
        f[n % (d + 1)] = 1;
        for (int i = n - 1; i >= 0; --i) {
            int ways = 0;
            if (s[i] != '0') {
                long long value = 0;
                for (int j = i; j < n && j < i + d; ++j) {
                    value = value * 10 + s[j] - '0';
                    if (value > k) break;
                    ways = (ways + f[(j + 1) % (d + 1)]) % mod;
                }
            }
            f[i % (d + 1)] = ways;
        }
        return f[0];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function numberOfArrays(s: string, k: number): number {
    const mod = 1e9 + 7;
    const n = s.length;
    const d = String(k).length;
    const f = Array(d + 1).fill(0);
    f[n % (d + 1)] = 1;
    for (let i = n - 1; i >= 0; --i) {
        let ways = 0;
        if (s[i] !== '0') {
            let value = 0;
            for (let j = i; j < n && j < i + d; ++j) {
                value = value * 10 + s.charCodeAt(j) - 48;
                if (value > k) {
                    break;
                }
                ways = (ways + f[(j + 1) % (d + 1)]) % mod;
            }
        }
        f[i % (d + 1)] = ways;
    }
    return f[0];
}

评论