Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1849.html
1849. Splitting a String Into Descending Consecutive Values
Level
Medium
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.
Example 4:
Input: s = “10009998”
Output: true
Explanation: s can be split into [“100”, “099”, “98”] with numerical values [100,99,98].
The values are in descending order with adjacent values differing by 1.
Constraints:
1 <= s.length <= 20
s
only consists of digits.
Solution
Use backtrack to find a way to split the string. If the current substring represents a numerical value that is less than the previous numerical value by 1, then split the current substring. If the end of the string is reached and there are at least two parts, return true
. If no such a way is found, return false
.
-
class Solution { public boolean splitString(String s) { int length = s.length(); long firstNum = 0; for (int i = 0; i < length - 1; i++) { firstNum = firstNum * 10 + (s.charAt(i) - '0'); boolean flag = backtrack(s, 1, firstNum, i + 1); if (flag) return true; } return false; } public boolean backtrack(String s, int count, long prev, int start) { int length = s.length(); if (start == length) return count > 1; for (int i = start + 1; i <= length; i++) { String currStr = s.substring(start, i); long curr = Long.parseLong(currStr); if (curr >= prev) break; if (prev - curr == 1) { boolean flag = backtrack(s, count + 1, curr, i); if (flag) return true; } } return false; } }
-
// OJ: https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values/ // Time: O(N!) // Space: O(N) class Solution { bool valid(string &prev, string cur) { if (prev == "") return true; reverse(begin(cur), end(cur)); int carry = 1; for (char &c : cur) { carry += c - '0'; c = '0' + carry % 10; carry /= 10; } if (carry) cur.push_back('1'); reverse(begin(cur), end(cur)); return prev == cur; } bool dfs(string &s, int start, string prev = "") { if (start == s.size()) { return true; } while (start + 1 < s.size() && s[start] == '0') ++start; for (int i = start + 1; i <= s.size() - (prev == ""); ++i) { auto sub = s.substr(start, i - start); if (valid(prev, sub) && dfs(s, i, sub)) return true; } return false; } public: bool splitString(string s) { return dfs(s, 0); } };
-
# 1849. Splitting a String Into Descending Consecutive Values # https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values class Solution: def splitString(self, s: str) -> bool: n = len(s) def go(i, prev): if i == n: return True valid = False for index in range(i + 1, n + 1): if int(s[i:index]) == prev - 1: valid |= go(index, prev - 1) if valid: return True return valid for i in range(1, n): if go(i, int(s[:i])): return True return False
-
func splitString(s string) bool { var dfs func(i, x, k int) bool dfs = func(i, x, k int) bool { if i == len(s) { return k > 1 } y := 0 for j := i; j < len(s); j++ { y = y*10 + int(s[j]-'0') if y > int(1e10) { break } if (x == -1 || x-y == 1) && dfs(j+1, y, k+1) { return true } } return false } return dfs(0, -1, 0) }