Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package dfs;
- class SteppingNumber {
- public static void findSteppingNum(int start, int end) {
- if(start > end) {
- System.out.println("Invalid input");
- return;
- }
- int tend = end;
- int tstart = start;
- int digitCount = 0;
- //find the very first digit of start; digitCount will be the depth of DFS
- while (tstart >= 10) {
- tstart /= 10;
- tend /= 10;
- digitCount++; //the number of digit needs to be filled out
- }
- int diff = tend - tstart;
- for(int i=0; i<=diff; i++) {
- //make sure the starting num is stepping number
- if(isStepping(tstart + i))
- helper(tstart + i, digitCount, start, end);
- }
- }
- public static void helper(int currNum, int remains, int start, int end) {
- if(remains == 0) {
- if(start <= currNum && currNum <= end) {
- System.out.println(currNum);
- }
- return;
- }
- int endDigit = currNum%10;
- //step down
- if(endDigit > 1) {
- int down = currNum*10 + endDigit - 1;
- helper(down, remains - 1, start, end);
- }
- //step up
- if(endDigit < 9) {
- int up = currNum*10 + endDigit + 1;
- helper(up, remains - 1, start, end);
- }
- }
- public static boolean isStepping(int num) {
- int lastDigit = num%10;
- num /= 10;
- while(num > 0) {
- int currentDigit = num%10;
- if(!(lastDigit - 1 == currentDigit || lastDigit + 1 == currentDigit))
- return false;
- num/=10;
- }
- return true;
- }
- public static void main(String...args) {
- findSteppingNum(1, 500); //23
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement