Welcome to Subscribe On Youtube

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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values/
    // 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);
        }
    };
    
  • # 1849. Splitting a String Into Descending Consecutive Values
    # https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values
    
    class Solution:
        def splitString(self, s: str) -> bool:
            n = len(s)
            
            def go(i, prev):
                if i == n: return True
                
                valid = False
                for index in range(i + 1, n + 1):
                    if int(s[i:index]) == prev - 1:
                        valid |= go(index, prev - 1)
                    
                    if valid: return True
                    
                return valid
            
            for i in range(1, n):
                if go(i, int(s[:i])):
                    return True
            
            return False
                
    
    
  • 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)
    }
    

All Problems

All Solutions