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;↵
}↵
}↵
~~~~~
↵
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;↵
}↵
}↵
~~~~~