2522. Partition String Into Substrings With Values at Most K

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics:
  • \(\color{blue}\textsf{Weekly Contest 323}\)

一、題目

You are given a string s consisting of digits from 1 to 9 and an integer k.
A partition of a string s is called good if:

  • Each digit of s is part of exactly one substring.
  • The value of each substring is less than or equal to k. Return the minimum number of substrings in a good partition of s. If no good partition of s exists, return -1.
    Note that:
  • The value of a string is its result when interpreted as an integer. For example, the value of "123" is 123 and the value of "1" is 1.
  • A substring is a contiguous sequence of characters within a string.

Example 1:

  • Input: s = “165462”, k = 60
  • Output: 4
  • Explanation: We can partition the string into substrings “16”, “54”, “6”, and “2”. Each substring has a value less than or equal to k = 60.
    It can be shown that we cannot partition the string into less than 4 substrings.

Example 2:

  • Input: s = “238182”, k = 60
  • Output: -1
  • Explanation: There is no good partition for this string.

Constraints:

  • 1 <= s.length <= 105
  • s[i] is a digit from '1' to '9'.
  • 1 <= k <= 10^9

二、分析

  • 用動態規劃的方式解題，將 dp[i] 定義為前 i 個字元的最小 minimumPartition。
  • 動態轉移方程式是，當 s[i:j] 滿足 <= k 的條件時， dp[j] = min(dp[j], dp[i]+1)。
  • 要注意如果直接將字串轉為數字(stoi)比較，可能會有超出整數範圍而報錯。在此我們可能用字串比較，先比較長度，再比較值。
if (s.length() > to_string(k).length()) return false;
else if (s.length() < to_string(k).length()) return true;
else return s <= to_string(k);

三、解題

1. DP

  • Time complexity: \(O(n^2)\)
  • Space complexity: \(O(n)\)
int minimumPartition(string s, int k) {
    int n = s.length();
    vector<int> dp(n+1, 100001);        // 因為 s 長度最大為 100000，故我們假定 dp 初始值為 100001
    dp[0] = 0;
    for (int right = 1; right <= n; right++) {
        for (int left = right-1; left >= 0; left--) {
            if (helper(s, left, right, k)) {
                dp[right] = min(dp[right], dp[left] + 1);   // 動態轉移
            } else {
                break;      // pruning，如果當下不滿足 k，那麼再加字元也不會滿足，故可以直接 break
            }
        }
    }
    return dp[n] >= 100001 ? -1 : dp[n];          // 注意最後的回傳值，
}
bool helper(string& s, int left, int right, int k) {
    int len = right - left;
    string subseq = s.substr(left, len);
    if (subseq.length() > to_string(k).length()) return false;
    else if (subseq.length() < to_string(k).length()) return true;
    return subseq <= to_string(k);
}

回目錄 Catalog