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

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

All Problems

All Solutions