1849-SplittingAStringIntoDescendingConsecutiveValues.go

package main

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

import "fmt"
import "strconv"

func splitString(s string) bool {
    IsValid := func(s string, t string) bool {
        si, _ := strconv.Atoi(s)
        ti, _ := strconv.Atoi(t)
        return (si - ti) == 1
    }
    var dfs func(i int, count int, prev string) bool
    dfs = func(i int, count int, prev string) bool {
        if i == len(s) && count > 1 { return true }
        for j := i; j < len(s); j++ {
            if prev == "" || IsValid(prev, s[i:j+1]) {
                if dfs(j + 1, i + 1, s[i:j+1]) { return true }
            }
        }
        return false
    }
    return dfs(0, 0, "")
}

func main() {
    // Example 1:
    // Input: s = "1234"
    // Output: false
    // Explanation: There is no valid way to split s.
    fmt.Println(splitString("1234")) // false
    // 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.
    fmt.Println(splitString("050043")) // true
    // Example 3:
    // Input: s = "9080701"
    // Output: false
    // Explanation: There is no valid way to split s.
    fmt.Println(splitString("9080701")) // false

    fmt.Println(splitString("999999999999999999")) // false
    fmt.Println(splitString("000000000000000000")) // false
}