Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1291.html

1291. Sequential Digits (Medium)

An integer has sequential digits if and only if each digit in the number is one more than the previous digit.

Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.

 

Example 1:

Input: low = 100, high = 300
Output: [123,234]

Example 2:

Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]

 

Constraints:

• 10 <= low <= high <= 10^9

Related Topics:
Backtracking

Solution 1.

• Java
• C++

• class Solution {
      public List<Integer> sequentialDigits(int low, int high) {
          if (high == 1000000000)
              high--;
          List<Integer> list = new ArrayList<Integer>();
          int lengthLow = String.valueOf(low).length(), lengthHigh = String.valueOf(high).length();
          List<Integer> listLow = sequentialDigitsWithLength(lengthLow);
          for (int num : listLow) {
              if (num > high)
                  break;
              if (num >= low)
                  list.add(num);
          }
          for (int i = lengthLow + 1; i < lengthHigh; i++) {
              List<Integer> listWithLength = sequentialDigitsWithLength(i);
              for (int num : listWithLength)
                  list.add(num);
          }
          List<Integer> listHigh = sequentialDigitsWithLength(lengthHigh);
          if (lengthLow < lengthHigh) {
              for (int num : listHigh) {
                  if (num <= high)
                      list.add(num);
                  else
                      break;
              }
          }
          return list;
      }
  
      public List<Integer> sequentialDigitsWithLength(int length) {
          List<Integer> list = new ArrayList<Integer>();
          int begin = 1, end = 9 - length + 1;
          int num = 0;
          int inc = 0;
          int digit = 1;
          while (digit <= length) {
              num *= 10;
              num += digit;
              digit++;
              inc *= 10;
              inc++;
          }
          for (int i = begin; i <= end; i++) {
              list.add(num);
              num += inc;
          }
          return list;
      }
  }
  

• // OJ: https://leetcode.com/problems/sequential-digits/
  // Time: O(1) since there are limited number of valid integers
  // Space: O(1)
  class Solution {
      long get(int start, int len) {
          long ans = 0;
          while (len-- > 0) {
              ans = ans * 10 + start;
              ++start;
          }
          return ans;
      }
  public:
      vector<int> sequentialDigits(int low, int high) {
          vector<int> ans;
          int len = 0;
          for (int tmp = low; tmp; tmp /= 10) ++len;
          while (len <= 9) {
              for (int i = 1; i <= 9 - len + 1; ++i) {
                  long long n = get(i, len);
                  if (n < low) continue;
                  if (n > high) return ans;
                  ans.push_back(n);
              }
              ++len;
          }
          return ans;
      }
  };
  

All Problems

All Solutions