forked from varunu28/LeetCode-Java-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRestore The Array.java
More file actions
31 lines (28 loc) · 833 Bytes
/
Restore The Array.java
File metadata and controls
31 lines (28 loc) · 833 Bytes
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
30
31
class Solution {
private static final int MOD = 1000_000_007;
public int numberOfArrays(String s, int k) {
int n = s.length();
int[] dp = new int[n + 1];
return dfs(dp, 0, s, k);
}
private int dfs(int[] dp, int start, String s, int k) {
if (dp[start] != 0) {
return dp[start];
}
if (start == s.length()) {
return 1;
}
if (s.charAt(start) == '0') {
return 0;
}
int count = 0;
for (int end = start; end < s.length(); end++) {
String currNum = s.substring(start, end + 1);
if (Long.parseLong(currNum) > k) {
break;
}
count = (count + dfs(dp, end + 1, s, k)) % MOD;
}
return dp[start] = count;
}
}