Question

1849. Splitting a String Into Descending Consecutive Values

中文文档

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.

 

Constraints:

• 1 <= s.length <= 20
• s only consists of digits.

Solutions

Solution 1: DFS (Depth-First Search)

Starting from the first character of the string, enumerate all possible split positions. Check if the split substring meets the requirements of the problem. If it does, continue to recursively check whether the remaining substring meets the requirements, until the entire string is traversed.

The time complexity is $O(n^2)$, and the space complexity is $O(n)$. Where $n$ is the length of the string.

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

    return dfs(0, -1, 0)

class Solution {
  private String s;

  public boolean splitString(String s) {
    this.s = s;
    return dfs(0, -1, 0);
  }

  private boolean dfs(int i, long x, int k) {
    if (i == s.length()) {
      return k > 1;
    }
    long y = 0;
    for (int j = i; j < s.length(); ++j) {
      y = y * 10 + (s.charAt(j) - '0');
      if ((x == -1 || x - y == 1) && dfs(j + 1, y, k + 1)) {
        return true;
      }
    }
    return false;
  }
}

class Solution {
public:
  bool splitString(string s) {
    function<bool(int, long long, int)> dfs = [&](int i, long long x, int k) -> bool {
      if (i == s.size()) {
        return k > 1;
      }
      long long y = 0;
      for (int j = i; j < s.size(); ++j) {
        y = y * 10 + (s[j] - '0');
        if (y > 1e10) {
          break;
        }
        if ((x == -1 || x - y == 1) && dfs(j + 1, y, k + 1)) {
          return true;
        }
      }
      return false;
    };
    return dfs(0, -1, 0);
  }
};

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)
}