Google – Generate All Numbers in Range

Google – Generate All Numbers in Range
给两个string a和b表示两个数，输出a和b之间所有的数。假设a对应位的digit都小于等于b。
比如a = 123, b = 234, 或者a = 123, b = 2123.
a = 99, b = 100这样的就不行。
[Solution]
看着就像backtracking题。不过这题backtracking还得分情况考虑:

1. 如果sb[i – 1] == a[i – 1]，那么当前level从a[i]开始，否则从0开始。
2. 如果sb[i – 1] == b[i – 1]，那么当前level到b[i]结束，否则到9结束。

上面两种情况可能同时出现，也可能单独出现。
[Note]
这道题用string也就是防止overflow，其实如果输入两个integer，backtracking和直接用for loop遍历的复杂度是一样的。

  public List<String> allNumbers(String a, String b) {

    List<String> result = new ArrayList<>();

    while (a.length() < b.length()) {

      a = "0" + a;

    }

 

    backtracking(a, b, 0, result, new StringBuilder());

    return result;

  }

 

  private void backtracking(String a, String b, int pos, List<String> result, StringBuilder sb) {

    if (pos == a.length()) {

      result.add(sb.toString());

      return;

    }

 

    int i = 0;

    if (pos == 0 || sb.charAt(pos - 1) == a.charAt(pos - 1)) {

      i = a.charAt(pos) - '0';

    }

 

    int j = 9;

    if (pos == 0 || sb.charAt(pos - 1) == b.charAt(pos - 1)) {

      j = b.charAt(pos) - '0';

    }

 

    while (i <= j) {

      sb.append(i);

      if (i < j) {

        backtracking(a, b, pos + 1, result, sb);

      }

      else {

        backtracking(a, b, pos + 1, result, sb);

      }

      sb.deleteCharAt(sb.length() - 1);

      i++;

    }

  }

Read full article from Google – Generate All Numbers in Range