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