ปัญหา
มีสตริง s ที่เกิดจากการพิมพ์อาร์เรย์ตัวเลขติดกัน (ไม่มี space) โดยแต่ละตัวเลขอยู่ในช่วง [1, k] หาจำนวนวิธีแบ่งสตริงกลับเป็นอาร์เรย์ที่ถูกต้อง คำตอบ modulo 10^9 + 7
ตัวอย่าง: s = "1318", k = 2000 → 8 วิธี:
[1318], [131,8], [13,18], [1,318], [1,3,18], [1,31,8], [13,1,8], [1,3,1,8]
แนวคิด: Dynamic Programming (Bottom-Up)
State
ans[i] = จำนวนวิธีแบ่ง prefix s[0..i-1] (ความยาว i)
Base Case
ans[0] = 1 (สตริงว่างมี 1 วิธี)
Transition
สำหรับแต่ละ i = 1..n พิจารณาตัวเลขสุดท้ายที่จบที่ i-1 โดยดูย้อนหลังสูงสุด 10 หลัก (เพราะ k ≤ 10^9 มีสูงสุด 10 หลัก):
for j = i-1 downto max(0, i-10):
substring = s[j..i-1]
if substring[0] == '0': continue // ไม่มี leading zero
val = stoi(substring)
if 1 <= val <= k:
ans[i] += ans[j]
โค้ด C++
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MOD = 1e9 + 7;
class Solution {
lli add(lli a, lli b) {
return ((a % MOD) + (b % MOD)) % MOD;
}
public:
int numberOfArrays(string s, int k) {
int n = s.size();
vector<lli> ans(n + 1, 0);
ans[0] = 1;
s = " " + s; // 1-based indexing
string ks = to_string(k);
for (int i = 1; i <= n; i++) {
string temp = "";
for (int j = i, cnt = 1; j >= 1 && cnt <= 10; j--, cnt++) {
temp = s[j] + temp; // prepend
if (s[j] == '0') continue; // leading zero
if (temp.size() > ks.size()) break; // เกิน k แน่นอน
lli val = stoll(temp);
if (val >= 1 && val <= k) {
ans[i] = add(ans[i], ans[j - 1]);
}
}
}
return ans[n];
}
};
int main() {
Solution ob;
cout << ob.numberOfArrays("1318", 2000); // 8
return 0;
}
การเพิ่มประสิทธิภาพ (Memoization Top-Down)
อีกวิธีหนึ่งใช้ Recursion + Memoization:
unordered_map<int, unordered_map<lli, int>> dp;
int help(int idx, string& s, lli num, int k) {
if (idx >= s.size()) return 1;
if (dp.count(idx) && dp[idx].count(num)) return dp[idx][num];
int ret = 0;
// ตัดทอน: ใช้ num ที่สร้างมาแล้วเป็นตัวเลขตัวสุดท้าย
if (num >= 1 && num <= k && s[idx] != '0') {
ret = add(help(idx, s, 0, k), ret); // เริ่มตัวเลขใหม่
}
// ต่อตัวเลขเดิม
if (num * 10 + (s[idx] - '0') <= k) {
ret = add(help(idx + 1, s, num * 10 + (s[idx] - '0'), k), ret);
}
return dp[idx][num] = ret;
}
ความซับซ้อน
- Time: O(n × 10) = O(n) - แต่ละตำแหน่งดูย้อนหลังสูงสุด 10 ตัว
- Space: O(n)
Input / Output
Input: "1318", 2000
Output: 8
