Skip to content

1977. Number of Ways to Separate Numbers 👍

  • Time:
  • Space: 
 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
 public:
  int numberOfCombinations(string num) {
    if (num[0] == '0')
      return 0;

    constexpr int kMod = 1'000'000'007;
    const int n = num.size();

    // dp[i][k] := number of possible lists of integers ending at num[i] with
    // the length of the last number being 1..k.
    vector<vector<long>> dp(n, vector<long>(n + 1));
    // lcs[i][j] := number of the same characters in num[i:] and num[j:].
    vector<vector<int>> lcs(n + 1, vector<int>(n + 1));

    for (int i = n - 1; i >= 0; --i)
      for (int j = i + 1; j < n; ++j)
        if (num[i] == num[j])
          lcs[i][j] = lcs[i + 1][j + 1] + 1;

    for (int i = 0; i < n; ++i)
      for (int k = 1; k <= i + 1; ++k) {
        dp[i][k] += dp[i][k - 1];
        dp[i][k] %= kMod;
        // The last number is num[s..i].
        const int s = i - k + 1;
        if (num[s] == '0')
          // Number of possible lists of integers ending at num[i] with the
          // length of the last number being k.
          continue;
        if (s == 0) {
          // The whole string.
          dp[i][k] += 1;
          continue;
        }
        if (s < k) {
          // Not enough length k, so add the number of possible lists of
          // integers in num[0..s - 1].
          dp[i][k] += dp[s - 1][s];
          continue;
        }
        const int l = lcs[s - k][s];
        if (l >= k || num[s - k + l] <= num[s + l])
          // Have enough length k and num[s - k..s - 1] <= num[j..i].
          dp[i][k] += dp[s - 1][k];
        else
          // Have enough length k but num[s - k..s - 1] > num[j..i].
          dp[i][k] += dp[s - 1][k - 1];
      }

    return dp[n - 1][n] % kMod;
  }
};

 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
  public int numberOfCombinations(String num) {
    if (num.charAt(0) == '0')
      return 0;

    final int kMod = 1_000_000_007;
    final int n = num.length();

    // dp[i][k] := number of possible lists of integers ending at num[i] with
    // the length of the last number being 1..k.
    long[][] dp = new long[n][n + 1];
    // lcs[i][j] := number of the same characters in num[i:] and num[j:].
    int[][] lcs = new int[n + 1][n + 1];

    for (int i = n - 1; i >= 0; --i)
      for (int j = i + 1; j < n; ++j)
        if (num.charAt(i) == num.charAt(j))
          lcs[i][j] = lcs[i + 1][j + 1] + 1;

    for (int i = 0; i < n; ++i)
      for (int k = 1; k <= i + 1; ++k) {
        dp[i][k] += dp[i][k - 1];
        dp[i][k] %= kMod;
        // The last number is num[s..i].
        final int s = i - k + 1;
        if (num.charAt(s) == '0')
          // Number of possible lists of integers ending at num[i] with the
          // length of the last number being k.
          continue;
        if (s == 0) {
          // The whole string.
          dp[i][k] += 1;
          continue;
        }
        if (s < k) {
          // Not enough length k, so add the number of possible lists of
          // integers in num[0..s - 1].
          dp[i][k] += dp[s - 1][s];
          continue;
        }
        final int l = lcs[s - k][s];
        if (l >= k || num.charAt(s - k + l) <= num.charAt(s + l))
          // Have enough length k and num[s - k..s - 1] <= num[j..i].
          dp[i][k] += dp[s - 1][k];
        else
          // Have enough length k but num[s - k..s - 1] > num[j..i].
          dp[i][k] += dp[s - 1][k - 1];
      }

    return (int) dp[n - 1][n] % kMod;
  }
}

 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution:
  def numberOfCombinations(self, num: str) -> int:
    if num[0] == '0':
      return 0

    kMod = 1_000_000_007
    n = len(num)
    # dp[i][k] := # of possible lists of integers ending at num[i] with the
    # length of the last number being 1..k
    dp = [[0] * (n + 1) for _ in range(n)]
    # lcs[i][j] := # of the same characters of num[i:] and num[j:]
    lcs = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(n - 1, -1, -1):
      for j in range(i + 1, n):
        if num[i] == num[j]:
          lcs[i][j] = lcs[i + 1][j + 1] + 1

    for i in range(n):
      for k in range(1, i + 2):  # since i is 0-indexed
        dp[i][k] += dp[i][k - 1]
        dp[i][k] %= kMod
        # The last number is num[s..i].
        s = i - k + 1
        if num[s] == '0':
          # number of possible lists of integers ending at num[i] with the
          # length of the last number being k
          continue
        if s == 0:  # the whole string
          dp[i][k] += 1
          continue
        if s < k:
          # Not enough length k, so add the number of possible lists of integers
          # in num[0..s - 1].
          dp[i][k] += dp[s - 1][s]
          continue
        l = lcs[s - k][s]
        if l >= k or num[s - k + l] <= num[s + l]:
          # Have enough length k and num[s - k..s - 1] <= num[j..i].
          dp[i][k] += dp[s - 1][k]
        else:
          # Have enough length k but num[s - k..s - 1] > num[j..i].
          dp[i][k] += dp[s - 1][k - 1]

    return dp[n - 1][n] % kMod