1849. Splitting a String Into Descending Consecutive Values - Explanation

Problem Link



1. Backtracking

class Solution:
    def splitString(self, s: str) -> bool:
        n = len(s)

        def isValid(splits):
            for i in range(1, len(splits)):
                if splits[i] != splits[i - 1] - 1:
                    return False
            return len(splits) > 1

        def dfs(i, splits):
            if i == n:
                return isValid(splits)
            num = 0
            for j in range(i, n):
                num = num * 10 + int(s[j])
                splits.append(num)
                if dfs(j + 1, splits):
                    return True
                splits.pop()
            return False

        return dfs(0, [])

Time & Space Complexity

  • Time complexity: O(nn)O(n ^ n)
  • Space complexity: O(n)O(n)

2. Recursion - I

class Solution:
    def splitString(self, s: str) -> bool:
        def dfs(index, prev):
            if index == len(s):
                return True
            num = 0
            for j in range(index, len(s)):
                num = num * 10 + int(s[j])
                if num + 1 == prev and dfs(j + 1, num):
                    return True
            return False

        val = 0
        for i in range(len(s) - 1):
            val = val * 10 + int(s[i])
            if dfs(i + 1, val):
                return True

        return False

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n)O(n) for recursion stack.

3. Recursion - II

class Solution:
    def splitString(self, s: str) -> bool:
        def dfs(index, prev):
            if index == len(s):
                return True
            num = 0
            for j in range(index, len(s)):
                num = num * 10 + int(s[j])
                if num + 1 == prev and dfs(j + 1, num):
                    return True
                if num >= prev:
                    break
            return False

        val = 0
        for i in range(len(s) - 1):
            val = val * 10 + int(s[i])
            if dfs(i + 1, val):
                return True

        return False

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n)O(n) for recursion stack.

4. Stack

class Solution:
    def splitString(self, s: str) -> bool:
        n = len(s)
        stack = []
        val = 0

        for i in range(n - 1):
            val = val * 10 + int(s[i])
            stack.append((i + 1, val))

            while stack:
                index, prev = stack.pop()
                num = 0
                for j in range(index, n):
                    num = num * 10 + int(s[j])
                    if num + 1 == prev:
                        if j + 1 == n:
                            return True
                        stack.append((j + 1, num))
                    elif num >= prev:
                        break

        return False

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n)O(n)