Program to check whether we can split a string into descending consecutive values in Python

Suppose we have a string s with only numbers. We have to check whether we can split s into two or more non-empty substrings such that the numerical values of those substrings are in non-increasing sequence and the difference between numerical values of every two adjacent substrings is 1. So for example, if the string is s = "0080079" we can split it into ["0080", "079"] with numerical values [80, 79]. And the values are in descending order and adjacent values differ by 1, so this way is valid. We have to check whether it is possible to split s as described above, or not.

So, if the input is like s = "080076", then the output will be True because we can split it like ["08", "007", "6"], so numeric values are [8,7,6].

To solve this, we will follow these steps −

• Define a function dfs() . This will take s, pre, idx, n

• if pre is not -1 and integer form of (substring of s[from index idx to end]) is same as pre -1, then

  • return True

• for i in range 1 to n-idx-1, do

  • curs := substring of s[from index idx to idx+i-1]

  • cur := curs as number

  • if pre is same as -1, then

    • if dfs(s, cur, idx+i, n) is true, then

      • return True

    • otherwise,

      • if cur is same as pre - 1 and dfs(s, cur, idx+i, n) is true, then

        • return True

• return False

• From the main method, do the following

• n := size of s

• if n <= 1, then

  • return False

• return dfs(s, -1, 0, n)

Example

Let us see the following implementation to get better understanding −

def dfs(s, pre, idx, n):    if pre != -1 and int(s[idx:]) == pre - 1:       return True    for i in range(1, n-idx):       curs = s[idx: idx+i]       cur = int(curs)       if pre == -1:          if dfs(s, cur, idx+i, n):             return True       else: if cur == pre - 1 and dfs(s, cur, idx+i, n): return True return False def solve(s): n = len(s) if n <= 1: return False return dfs(s, -1, 0, n) s = "080076" print(solve(s)) 

Input

"080076"

Output

True