Splitting a String Into Descending

lcpy gen -n 1849   # by problem number
lcpy gen -s splitting_a_string_into_descending_consecutive_values   # by problem name

Input: s = "1234"
Output: false
Explanation: There is no valid way to split s.

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.

Input: s = "9080701"
Output: false
Explanation: There is no valid way to split s.

from functools import cache


class Solution:
    # Time: O(n^2) states explored via DFS over cut positions
    # Space: O(n) for recursion depth and memoization
    def split_string(self, s: str) -> bool:
        n = len(s)

        @cache
        def dfs(i: int, prev: int) -> bool:
            if i == n:
                return True
            for j in range(i + 1, n + 1):
                val = int(s[i:j])
                if prev - val == 1 and dfs(j, val):
                    return True
            return False

        # The first piece must leave at least one character for a second piece.
        return any(dfs(j, int(s[:j])) for j in range(1, n))