1849

1849. Splitting a String Into Descending Consecutive Values (Medium)

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.

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.

Related Topics:
String, Backtracking, Recursion

Solution 1.

// OJ: https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values/
// Author: github.com/lzl124631x
// 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);
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values/
// Author: github.com/lzl124631x
// Time: O(N!)
// Space: O(N)
class Solution {
    bool dfs(string &s, int start, long long prev = -1) {
        if (start == s.size()) {
            return true;
        }
        while (start + 1 < s.size() && s[start] == '0') ++start; // it's important to skip leading zeros. Otherwise the substring could be too long for `stoll`
        for (int i = start + 1; i <= s.size() - (prev == -1); ++i) {
            if (i - start > 10) break; // the original string is at most 20 characters long, so skip if the length of the substring is more than 10.
            auto sub = s.substr(start, i - start);
            long long n = stoll(sub);
            if (prev == -1 || n == prev - 1) {
                if (dfs(s, i, n)) return true;
            }
        }
        return false;
    }
public:
    bool splitString(string s) {
        return dfs(s, 0);
    }
};