MediumNo. 1849
Splitting a String Into Descending Consecutive Values — LeetCode 1849 Python Solution
- Pattern
- Backtracking
- Topics
- String, Backtracking, Enumeration
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given a string s that consists of only digits. Check if we can split s into two or more non-empty substrings such that the numerical values of the substrings are in descending order and the difference between numerical values of every two adjacent substrings is equal to 1.
Example
- Input
- s = "1234"
- Output
- false
- Explanation
- There is no valid way to split s.
Python solution
class Solution:
def splitString(self, s: str) -> bool:
def dfs(i: int, x: int) -> bool:
if i >= len(s):
return True
y = 0
r = len(s) - 1 if x < 0 else len(s)
for j in range(i, r):
y = y * 10 + int(s[j])
if (x < 0 or x - y == 1) and dfs(j + 1, y):
return True
return False
return dfs(0, -1)Complexity
- Time
- O(n2)
- Space · auxiliary
- O(n)where n is the length of the string
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1849. Splitting a String Into Descending Consecutive Values is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0816 | Ambiguous Coordinates | Medium |
| 0949 | Largest Time for Given Digits | Medium |
| 0079 | Word Search | Medium |
| 0093 | Restore IP Addresses | Medium |
| 0212 | Word Search II | Hard |
| 0257 | Binary Tree Paths | Easy |
Frequently asked questions
- How hard is LeetCode 1849. Splitting a String Into Descending Consecutive Values?
LeetCode 1849. Splitting a String Into Descending Consecutive Values is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1849. Splitting a String Into Descending Consecutive Values?
The Python solution on this page runs in O(n2).
- What is the space complexity of LeetCode 1849. Splitting a String Into Descending Consecutive Values?
The Python solution on this page uses O(n), where n is the length of the string auxiliary space.
- What topics does LeetCode 1849. Splitting a String Into Descending Consecutive Values cover?
LeetCode 1849. Splitting a String Into Descending Consecutive Values is tagged String, Backtracking and Enumeration on LeetCode.