Java - Recursive


  • 0
    J

    Build left and right half separately, put them together at the end. Have to consider corner cases: 0 can't be the first digit, the middle can only be 0,1 or 8 if odd length.

        public List<String> findStrobogrammatic(int n) {
    	
    	List<String> ans = new ArrayList<> ();
    	if (n == 1) {
    		getStrobogrammatic(ans, "", "", 1);
    		return ans;
    	}
    	char rd;
    	for (char d : "1869".toCharArray()) {
    	    if (d == '6') {
    	        rd = '9';
    	    } else if (d == '9') {
    	        rd = '6';
    	    } else {
    	        rd = d;
    	    }
     		getStrobogrammatic(ans, String.valueOf(d), String.valueOf(rd), n - 2);
    	}
    	return ans;
    }
    
    private void getStrobogrammatic(List<String> ans, String left,
    		String right, int n) {
    	if (n == 0) {
    		ans.add(left + right);  //even length, build completed, add to results.
    	} else if (n == 1) {
        	for (char d : "018".toCharArray()) { //odd length, add a middle char and put them in results.
        		ans.add(left + d + right);
        	}	
    	} else {
    	    char rd;
    		for (char d : "01869".toCharArray()) {
    		    if (d == '6') {
    		        rd = '9';
    		    } else if (d == '9') {
    		        rd = '6';
    		    } else {
    		        rd = d;
    		    }
    			getStrobogrammatic(ans, left + d, rd + right, n - 2);
    		}
    	}
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.