NeetCode #503LC-1849MediumBacktracking
← Back to All Problems#503 · #1849 · Splitting a String Into Descending Consecutive Values(将字符串拆分为递减的连续值)
📌 Problem Statement & Constraints
Given a string
s of digits, return true if it can be split into two or more non-empty substrings whose integer values form a strictly decreasing sequence where each value is exactly 1 less than the previous. Constraints: 2 <= s.length <= 20.💡 Core Algorithmic Approaches
- Try every possible first substring, then recursively require each following substring to equal
prev - 1. - Because the required value is fixed, there is no branching after the first choice -- only the split position varies.
- A pruning: as the substring grows, its integer value increases, so once it exceeds
prev - 1, longer substrings cannot work either. - The answer requires at least two substrings, which the outer loop guarantees.
💻 Benchmark Python3 Implementation
class Solution:
def splitString(self, s: str) -> bool:
n = len(s)
def dfs(start: int, prev: int) -> bool:
if start == n:
return True # the whole string was consumed
for end in range(start, n):
cur = int(s[start:end + 1])
if cur == prev - 1 and dfs(end + 1, cur):
return True
if cur >= prev:
break # longer substrings are even larger
return False
for end in range(0, n - 1): # leave room for at least one more part
first = int(s[:end + 1])
if dfs(end + 1, first):
return True
return False⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): the first split has O(n) choices and each verification is O(n) amortised.
💾 Space Complexity
O(n) for the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Allowing the first substring to consume the whole string: at least two parts are required, hence
range(0, n - 1). - Using
continueinstead ofbreakfor thecur >= prevpruning:breakis valid because longer substrings are strictly larger. - Forgetting that leading zeros are allowed:
"10"splits into"1"and"0", since 0 = 1 - 1 -- the values need not have no leading zeros, only the values must satisfy the decrement rule. (Leading zeros inside a part are fine here.) - Requiring the sequence to be consecutive but not strictly decreasing by exactly 1: the rule is exactly
prev - 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.