LeetCode每日一题(1849. Splitting a String Into Descending Consecutive Values)

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.

---

不知道该怎么表达， 看代码吧

---

impl Solution {
    fn rc(digits: &[char], mut i: usize, prev: i128) -> bool {
        if i == digits.len() {
            return true;
        }
        let mut curr = 0;
        while curr < prev && i < digits.len() {
            // 每向右扩展一位，当前值*10+单个数字的值
            curr *= 10;
            curr += digits[i].to_string().parse::<i128>().unwrap();
            // 当前值正好比前一个值小1的时候， 此时如果后面的数组可以组成递减数列则证明整体可以形成递减数列
            if curr + 1 == prev && Solution::rc(digits, i + 1, curr) {
                return true;
            }
            // 就算当前值正好比前一个值小1了，也需要继续检查， 因为当前值可能为0， 后面则字符也可能为0， 这样扩展位数之后也不会使当前值增加
            i += 1;
        }
        // 考虑当前值是最后一个数的情况
        if curr + 1 == prev {
            return true;
        }
        false
    }
    pub fn split_string(s: String) -> bool {
        if s.len() == 1 {
            return false;
        }
        let digits: Vec<char> = s.chars().collect();
        let mut curr = 0;
        for i in 0..digits.len() - 1 {
            curr *= 10;
            curr += digits[i].to_string().parse::<i128>().unwrap();
            if Solution::rc(&digits, i + 1, curr) {
                return true;
            }
        }
        false
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40