1416. 恢复数组

Smile_slime_47
  1999-01-01 1999-01-01 Created    

原题地址：https://leetcode.cn/problems/restore-the-array/

题解

设dp[i]为s的子串s[0,i]的方案数

令j遍历i~0，自然地，我们可以将子串进一步切分为s[0,j-1]和[j,i]两部分

  • 同时，[j,i]这部分子串我们可以将其解析为一个新的数字num
  • 此时，若这个解析出来的数字满足条件（即），则s的子串s[0,i]的方案数变成了s的子串s[0,j-1]的方案数这个子问题

此时我们得到了一个基本的DP公式：

对于子串num[j,i]的解析数字：

对于任意j满足：

考虑到几种特殊情况：

  • 解析数字的范围在[1,k]，所以数字为0时可以直接continue
  • 解析数字不包含前导0，所以s[j]==0时可以直接continue
  • 解析数字必定小于等于k，当解析数字的位数大于k的位数或者解析数字大于k时，必定不存在解，可以直接break

对于边界情况，当j为0时，若子串[0,i]的解析数字满足情况，此时不存在dp[j-1]，方案数应为1，即

最后不要忘了对dp[i]%=1e9+7

时间复杂度：O(N^2)

空间复杂度：O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int numberOfArrays(String s, int k) {
        int digit=1,kcopy=k;
        while(kcopy>=10){
            kcopy/=10;
            digit++;
        }

        long[] dp=new long[s.length()];
        long num,pow;
        for(int i=0;i<s.length();i++){
            num=0;
            pow=1;
            for(int j=i;j>=0;j--){
                if(i-j+1>digit)break;
                num=num+(s.charAt(j)-'0')*pow;
                pow*=10;
                if(s.charAt(j)=='0'||num==0){
                    continue;
                }
                if(num<=k){
                    dp[i]+=j-1>=0?dp[j-1]:1;
                    dp[i]%=1000000007;
                }else break;
            }
        }
        return (int)(dp[s.length()-1]);
    }
}
Comments
On this page
1416. 恢复数组
  1. 题解