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 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

Starting from the first character of the string, enumerate all possible split positions. Check if the split substring meets the requirements of the problem. If it does, continue to recursively check whether the remaining substring meets the requirements, until the entire string is traversed.

The time complexity is $O(n^2)$, and the space complexity is $O(n)$. Where $n$ is the length of the string.

Python Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def splitString(self, s: str) -> bool:
        def dfs(i, x, k):
            if i == len(s):
                return k > 1
            y = 0
            for j in range(i, len(s)):
                y = y * 10 + int(s[j])
                if (x == -1 or x - y == 1) and dfs(j + 1, y, k + 1):
                    return True
            return False

        return dfs(0, -1, 0)

Java Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    private String s;

    public boolean splitString(String s) {
        this.s = s;
        return dfs(0, -1, 0);
    }

    private boolean dfs(int i, long x, int k) {
        if (i == s.length()) {
            return k > 1;
        }
        long y = 0;
        for (int j = i; j < s.length(); ++j) {
            y = y * 10 + (s.charAt(j) - '0');
            if ((x == -1 || x - y == 1) && dfs(j + 1, y, k + 1)) {
                return true;
            }
        }
        return false;
    }
}

C++ Code
 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) {
        function<bool(int, long long, int)> dfs = [&](int i, long long x, int k) -> bool {
            if (i == s.size()) {
                return k > 1;
            }
            long long y = 0;
            for (int j = i; j < s.size(); ++j) {
                y = y * 10 + (s[j] - '0');
                if (y > 1e10) {
                    break;
                }
                if ((x == -1 || x - y == 1) && dfs(j + 1, y, k + 1)) {
                    return true;
                }
            }
            return false;
        };
        return dfs(0, -1, 0);
    }
};

Go Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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)
}