Skip to content

1849. Splitting a String Into Descending Consecutive Values 👍

  • Time: $O(2^n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  bool splitString(string s) {
    return isValid(s, 0, -1, 0);
  }

 private:
  bool isValid(const string& s, int start, long prev, int segment) {
    if (start == s.length() && segment > 1)
      return true;

    long curr = 0;
    for (int i = start; i < s.length(); ++i) {
      curr = curr * 10 + s[i] - '0';
      if (curr > 9999999999L)
        return false;
      if ((prev == -1 || curr == prev - 1) &&
          isValid(s, i + 1, curr, segment + 1)) {
        return true;
      }
    }

    return false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public boolean splitString(String s) {
    return isValid(s, 0, -1, 0);
  }

  private boolean isValid(final String s, int start, long prev, int segment) {
    if (start == s.length() && segment > 1)
      return true;

    long curr = 0;
    for (int i = start; i < s.length(); ++i) {
      curr = curr * 10 + s.charAt(i) - '0';
      if (curr > 9999999999)
        return false;
      if ((prev == -1 || curr == prev - 1) && isValid(s, i + 1, curr, segment + 1))
        return true;
    }

    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def splitString(self, s: str) -> bool:
    def isValid(s: str, start: int, prev: int, segment: int) -> bool:
      if start == len(s) and segment > 1:
        return True

      curr = 0
      for i in range(start, len(s)):
        curr = curr * 10 + int(s[i])
        if curr > 9999999999:
          return False
        if (prev == -1 or curr == prev - 1) and isValid(s, i + 1, curr, segment + 1):
          return True

      return False

    return isValid(s, 0, -1, 0)