Intuition

We want to split the string into non-decreasing positive integers with no leading zeros. For each position, we can try all possible previous splits and check if the new number is at least as large as the previous. To compare large numbers efficiently, we use precomputed LCP (longest common prefix) arrays.

Approach

Precompute the LCP array for all pairs of positions in the string.
Use DP: let dp[i] be the number of ways to split the prefix num[:i].
For each end position i, try all possible start positions j < i, and if num[j:i] is valid and non-decreasing, add dp[j] to dp[i].
Use the LCP array to compare num[j-k:j] and num[j:i] efficiently.
Return dp[n].

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int numberOfCombinations(string num) {\n        int n = num.size(), mod = 1e9+7;\n        if (num[0] == '0') return 0;\n        vector<vector<int>> lcp(n+1, vector<int>(n+1));\n        for (int i = n-1; i >= 0; --i)\n            for (int j = n-1; j >= 0; --j)\n                lcp[i][j] = (num[i] == num[j] ? lcp[i+1][j+1]+1 : 0);\n        vector<vector<int>> dp(n+1, vector<int>(n+1));\n        for (int i = 1; i <= n; ++i) {\n            for (int k = 1; k <= i; ++k) {\n                if (num[i-k] == '0') continue;\n                if (i-k == 0) { dp[i][k] = 1; continue; }\n                int j = i-k;\n                if (j-k >= 0) {\n                    int cmp = lcp[j-k][i-k];\n                    if (cmp >= k || num[j-k+cmp] <= num[i-k+cmp])\n                        dp[i][k] = (dp[i][k] + dp[j][k]) % mod;\n                }\n                for (int t = 1; t < k && j-t >= 0; ++t)\n                    dp[i][k] = (dp[i][k] + dp[j][t]) % mod;\n            }\n        }\n        int ans = 0;\n        for (int k = 1; k <= n; ++k) ans = (ans + dp[n][k]) % mod;\n        return ans;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func numberOfCombinations(num string) int {\n    n, mod := len(num), int(1e9+7)\n    if num[0] == '0' { return 0 }\n    lcp := make([][]int, n+1)\n    for i := range lcp { lcp[i] = make([]int, n+1) }\n    for i := n-1; i >= 0; i-- {\n        for j := n-1; j >= 0; j-- {\n            if num[i] == num[j] {\n                lcp[i][j] = lcp[i+1][j+1] + 1\n            }\n        }\n    }\n    dp := make([][]int, n+1)\n    for i := range dp { dp[i] = make([]int, n+1) }\n    for i := 1; i <= n; i++ {\n        for k := 1; k <= i; k++ {\n            if num[i-k] == '0' { continue }\n            if i-k == 0 { dp[i][k] = 1; continue }\n            j := i-k\n            if j-k >= 0 {\n                cmp := lcp[j-k][i-k]\n                if cmp >= k || num[j-k+cmp] <= num[i-k+cmp] {\n                    dp[i][k] = (dp[i][k] + dp[j][k]) % mod\n                }\n            }\n            for t := 1; t < k && j-t >= 0; t++ {\n                dp[i][k] = (dp[i][k] + dp[j][t]) % mod\n            }\n        }\n    }\n    ans := 0\n    for k := 1; k <= n; k++ { ans = (ans + dp[n][k]) % mod }\n    return ans\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int numberOfCombinations(String num) {\n        int n = num.length(), mod = 1_000_000_007;\n        if (num.charAt(0) == '0') return 0;\n        int[][] lcp = new int[n+1][n+1];\n        for (int i = n-1; i >= 0; i--)\n            for (int j = n-1; j >= 0; j--)\n                lcp[i][j] = (num.charAt(i) == num.charAt(j) ? lcp[i+1][j+1]+1 : 0);\n        int[][] dp = new int[n+1][n+1];\n        for (int i = 1; i <= n; i++) {\n            for (int k = 1; k <= i; k++) {\n                if (num.charAt(i-k) == '0') continue;\n                if (i-k == 0) { dp[i][k] = 1; continue; }\n                int j = i-k;\n                if (j-k >= 0) {\n                    int cmp = lcp[j-k][i-k];\n                    if (cmp >= k || num.charAt(j-k+cmp) <= num.charAt(i-k+cmp))\n

Related Tags