# Simon in the boss

unknown
plain_text
7 months ago
2.1 kB
1
Indexable
Never
```class Solution {
#define Mod (int)(1e9+7)
#define Max 3505
public:
bool dpVisited[Max][Max], compareVisited[Max][Max];
int dp[Max][Max], length;
short compare[Max][Max];
string str;

// This compares the same length string that starts at position pre
// and string that starts at cur.
// If it returns -1 that means strings of same length starting from cur
// are always bigger (or equal to) than string of the same length starting from pre.
// if it returns a nonnegative number ret, that means we can only go ret distance
// from pre and cur , after that pre becomes bigger than cur.
int compareFunc(int pre, int cur){
if(cur == length) return -1;
if(compareVisited[pre][cur])
return compare[pre][cur];

compareVisited[pre][cur] = true;

if(str[pre] != str[cur]){
if(str[cur] > str[pre]) return compare[pre][cur] = -1;
return compare[pre][cur] = 0;

}
int val = compareFunc(pre + 1, cur +1);
if(val == -1) return compare[pre][cur] = -1;
return compare[pre][cur] = val + 1;
}

// This counts the number of result where current number starts at pos
// and the last number was of length len.
int dpFunc(int pos, int len){

if(pos > length) return 0;
if(pos == length) return 1;

if(dpVisited[pos][len])
return dp[pos][len];

dpVisited[pos][len] = true;

int ret = dpFunc(pos+1, len +1);

if(str[pos]=='0' || pos+len > length)
return dp[pos][len] = ret;

int curLen = len + 1;
int val = compareFunc(pos-len, pos);

if(val ==-1 || val >=len)
curLen--;

if(pos + curLen > length)
return dp[pos][len] = ret;

ret = (ret + dpFunc(pos + curLen, curLen) )%Mod;

return dp[pos][len] = ret;

}
int numberOfCombinations(string num) {
str = num;
length = str.length();

if(str[0] =='0') return 0;

return dpFunc(1,1);

}
};```