LeetCode 1849. Splitting a String Into Descending Consecutive Values Solution in Java, C++, Python & More | Explanation + Code

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 by 1, 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 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 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 true, we have found a valid split method and return true.

After traversing all possible split methods, if no valid split method is found, we return false.

The time complexity is O(n²), and the space complexity is O(n), where n is the length of the string.

PythonJavaC++GoTypeScript

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)(code-box)

class Solution { private char[] s; public boolean splitString(String s) { this.s = s.toCharArray(); return dfs(0, -1); } private boolean dfs(int i, long x) { if (i >= s.length) { return true; } long y = 0; int r = x < 0 ? s.length - 1 : s.length; for (int j = i; j < r; ++j) { y = y * 10 + s[j] - '0'; if ((x < 0 || x - y == 1) && dfs(j + 1, y)) { return true; } } return false; } }(code-box)

class Solution { public: bool splitString(string s) { auto dfs = [&](this auto&& dfs, int i, long long x) -> bool { if (i >= s.size()) { return true; } long long y = 0; int r = x < 0 ? s.size() - 1 : s.size(); for (int j = i; j < r; ++j) { y = y * 10 + s[j] - '0'; if (y > 1e10) { break; } if ((x < 0 || x - y == 1) && dfs(j + 1, y)) { return true; } } return false; }; return dfs(0, -1); } };(code-box)

func splitString(s string) bool { var dfs func(i, x int) bool dfs = func(i, x int) bool { if i >= len(s) { return true } y := 0 r := len(s) if x < 0 { r-- } for j := i; j < r; j++ { y = y*10 + int(s[j]-'0') if (x < 0 || x-y == 1) && dfs(j+1, y) { return true } } return false } return dfs(0, -1) }(code-box)

function splitString(s: string): boolean { const dfs = (i: number, x: number): boolean => { if (i >= s.length) { return true; } let y = 0; const r = x < 0 ? s.length - 1 : s.length; for (let j = i; j < r; ++j) { y = y * 10 + +s[j]; if ((x < 0 || x - y === 1) && dfs(j + 1, y)) { return true; } } return false; }; return dfs(0, -1); }(code-box)