Java Backtracking with StringBuilder 11ms


  • 0
    D
    private	char[] soles = {'0', '1' ,'8'};
    private String[] pairs = {"11", "69", "88", "96", "00"};
    public List<String> findStrobogrammatic(int n) {
    	List<String> res = new ArrayList<String>();
    	findStrobogrammatic(n, 0, new StringBuilder(), res);
    	return res;
    }
    private void findStrobogrammatic(int n, int index, StringBuilder sb, List<String> res) {
    	if (index == n / 2) { // terminate point
    		if (n % 2 == 1) { // if odd number, add middle digit
    			for (char sole : soles) {
    				sb.insert(index, sole);
    				res.add(sb.toString());
    				sb.deleteCharAt(index);
    			}
    		} else { // if even, directly add
    			res.add(sb.toString());
    		}
    	} else {
    		int len = index == 0 ? 3 : 4; // if first pair, cannot be "00".
    		for (int i = 0; i <= len; i++) {
    			sb.insert(index, pairs[i]);
    			findStrobogrammatic(n, index + 1, sb, res);
    			sb.delete(index, index + 2);
    		}
    	}
    }

Log in to reply
 

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