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: DFS
Time complexity: O(2n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { public: bool splitString(string s) { const int n = s.length(); vector<long> nums; function<bool(int)> dfs = [&](int p) { if (p == n) return nums.size() >= 2; long cur = 0; for (int i = p; i < n && cur < 1e11; ++i) { cur = cur * 10 + (s[i] - '0'); if (nums.empty() || cur + 1 == nums.back()) { nums.push_back(cur); if (dfs(i + 1)) return true; nums.pop_back(); } if (!nums.empty() && cur >= nums.back()) break; } return false; }; return dfs(0); } }; |