1416. Restore The Array

• 给一个字符串，求由这个字符串组成数字（小于k）的数量。
• https://leetcode.com/problems/restore-the-array/description/

思路

• 对于每次分割，都可以看成是前半段和后半段

• 前半段是确定的，可以用start和end取出来

• 后半段是一个递归函数

• 直到不剩下的时候，总数可以+1

• 如果过程中出现了开头是0，那么直接结束

• 前半段如果大于k了，那么，说明这里不能分割，后面的结果都不用看了

代码

class Solution {
    private int mod = (int) 1_000_000_007;
    private int get(int start, String s, int k, int[] dp){
        if(dp[start] != 0){
            return dp[start];
        }
        int count = 0;

        if(start == s.length()){
            return 1;
        }

        if(s.charAt(start) == '0'){
            return 0;
        }

        for(int end = start; end < s.length(); end++){
            Long num = Long.parseLong(s.substring(start, end + 1));
            if(num > k){
                break;
            }
            // System.out.println(count);
            count = (count + get(end + 1, s, k, dp)) % mod;
        }

        dp[start] = count;
        return count;
    }

    public int numberOfArrays(String s, int k) {
        return get(0, s, k, new int[s.length() + 1]);
    }
}