A DP solution based on @mach7 's solution


  • 0
    M
    public class Solution {
    public List<String> findStrobogrammatic(int n) {
    	List<List<String>> list = new ArrayList<List<String>>();
    	List<String> list_1 = new ArrayList<String>();
    	list_1.add("1");
    	list_1.add("8");
    	list_1.add("0");
    	list.add(list_1);
    	List<String> list_2 = new ArrayList<String>();
    	list_2.add("11");
    	list_2.add("88");
    	list_2.add("69");
    	list_2.add("96");
    	list_2.add("00");
    	list.add(list_2);
    	for(int i=2;i<n;i++){
    		List<String> newList = new ArrayList<String>();
    		List<String> baseList = list.get(i-2);
    		for(String string : baseList){
    			newList.add("1" + string + "1");
    			newList.add("8" + string + "8");
    			newList.add("6" + string + "9");
    			newList.add("9" + string + "6");
    			newList.add("0" + string + "0");		
    			
    		}
    		list.add(newList);
    	}
    	List<String> nthList = list.get(n-1);
    	List<String> result = new ArrayList<String>();
    	for(String string : nthList){
    		if(!(string.charAt(0) == '0')){
    			result.add(string);
    		}
    	}
    	if(n == 1) result.add("0");
    	return result;
    }
    

    }


Log in to reply
 

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