1849. Splitting a String Into Descending Consecutive Values
Description
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
.
- For example, the string
s = "0090089"
can be split into["0090", "089"]
with numerical values[90,89]
. The values are in descending order and adjacent values differ by1
, so this way is valid. - Another example, the string
s = "001"
can be split into["0", "01"]
,["00", "1"]
, or["0", "0", "1"]
. However all the ways are invalid because they have numerical values[0,1]
,[0,1]
, and[0,0,1]
respectively, all of which are not in descending order.
Return true
if it is possible to split s
as described above, or false
otherwise.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: s = "1234" Output: false Explanation: There is no valid way to split s.
Example 2:
Input: s = "050043" Output: true Explanation: s can be split into ["05", "004", "3"] with numerical values [5,4,3]. The values are in descending order with adjacent values differing by 1.
Example 3:
Input: s = "9080701" Output: false Explanation: There is no valid way to split s.
Constraints:
1 <= s.length <= 20
s
only consists of digits.
Solutions
Solution 1: DFS
We can start from the first character of the string and try to split it into one or more substrings, then recursively process the remaining part.
Specifically, we design a function $\textit{dfs}(i, x)$, where $i$ represents the current position being processed, and $x$ represents the last split value. Initially, $x = -1$, indicating that we have not split out any value yet.
In $\textit{dfs}(i, x)$, we first calculate the current split value $y$. If $x = -1$, or $x - y = 1$, then we can try to use $y$ as the next value and continue to recursively process the remaining part. If the result of the recursion is $\textit{true}$, we have found a valid split method and return $\textit{true}$.
After traversing all possible split methods, if no valid split method is found, we return $\textit{false}$.
The time complexity is $O(n^2)$, and the space complexity is $O(n)$, where $n$ is the length of the string.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|