Leetcode | Hard | Dynamic Programming | Help
Difference between en1 and en2, changed 37 character(s)
You wrote down many positive integers in a string called num. However, you realized that you forgot to add commas to seperate the different numbers. You remember that the list of integers was non-decreasing and that no integer had leading zeros.↵

Return the number of possible lists of integers that you could have written down to get the string num. Since the answer may be large, return it modulo 109 + 7.↵

Input: num = "327"↵
Output: 2↵
Explanation: You could have written down the numbers:↵
3, 27↵
327↵

Input: num = "094"↵
Output: 0↵
Explanation: No numbers can have leading zeros and all numbers must be positive.↵

Input: num = "0"↵
Output: 0↵
Explanation: No numbers can have leading zeros and all numbers must be positive.↵

Constraints:↵

1 <= num.length <= 3500↵
num consists of digits '0' through '9'.↵



Hi I have used mcm variation in this where i will traverse the depending on the condition wheather if i put comma then this particular string is equal or greater then previous↵
but my dp storage is not getting optimized please help me out!!↵



~~~~~↵
Your code here...↵

class Solution {↵
    public static int numberOfCombinations(String num) {↵
        HashMap<String,Integer> t= new HashMap<String,Integer>();↵
        return mcm_noOfComb("0",num,t);↵
    }↵
    public static int mcm_noOfComb(String s1,String s2,HashMap<String,Integer> t)↵
    {↵
        if(s2.length()==0)↵
            return 1;↵
        if(s2.charAt(0)=='0' || s2.length()<s1.length())↵
            return 0;↵
        if(s2.length()==s1.length())↵
        {↵
            int i=0;↵
            while(i<s1.length())↵
            {↵
                if(s2.charAt(i)<s1.charAt(i))↵
                {↵
                    return 0;↵
                }↵
            }↵
        }↵
        String key=s2;↵
        if(t.containsKey(key))↵
            return t.get(key);↵
        int k=0;↵
        while(k<s1.length())↵
        {    if(s2.charAt(k)<s1.charAt(k))↵
        {↵
            k=s1.length()+1;↵
            break;↵
        }↵
            k++;↵
        }↵
        int mod=(int)1e9+7;↵
        int cnt=0;↵
        for(int i=k;i<=s2.length();i++)↵
        {↵
            int temp = mcm_noOfComb(s2.substring(0,i),s2.substring(i,s2.length()),t)%mod;↵
            cnt = ((cnt%mod)+(temp%mod))%mod;↵
        }↵
        t.put(key,cnt);↵
        return cnt;↵
    }↵
}

~~~~~

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Utsav1998 2022-08-19 10:24:54 37
en1 English Utsav1998 2022-08-19 10:23:31 2379 Initial revision (published)