Java naive AC solution


  • 0
    V
    public class Solution {
        public List<String> findStrobogrammatic(int n) {
            if(n == 1) return Arrays.asList(new String[]{"0", "1", "8"});
            List<String> answer = new ArrayList<String>();
            List<List<String>> fromHelper = getList(n/2);
            List<String> first = fromHelper.get(0);
            List<String> second = fromHelper.get(1);
            if(n % 2 == 0){
                for(int i = 0; i < first.size(); i++){
                    if(first.get(i).charAt(0) != '0')
                        answer.add(first.get(i) + second.get(i));
                }
                return answer;
            }
            for(int i = 0; i < first.size(); i++){
                if(first.get(i).charAt(0) != '0'){
                    answer.add(first.get(i) + "0" + second.get(i));
                    answer.add(first.get(i) + "1" +second.get(i));
                    answer.add(first.get(i) + "8" +second.get(i));
                }
            }
            return answer;
        }
        private List<List<String>> getList(int n){
            if(n == 1) {
                List<String> first = new ArrayList<String>();
                List<String> second = new ArrayList<String>();
                first.add("0");first.add("1");first.add("8");first.add("6");first.add("9");
                second.add("0");second.add("1");second.add("8");second.add("9");second.add("6");
                List<List<String>> list = new ArrayList<List<String>>();
                list.add(first);
                list.add(second);
                return list;
            }
            List<List<String>> list = getList(n-1);
            List<String> first = list.get(0);
            List<String> second = list.get(1);
            List<String> newFirst = new ArrayList<String>();
            List<String> newSecond = new ArrayList<String>();
            for(String s : first) newFirst.add(s+"0");
            for(String s : first) newFirst.add(s+"1");
            for(String s : first) newFirst.add(s+"8");
            for(String s : first) newFirst.add(s+"6");
            for(String s : first) newFirst.add(s+"9");
            
            for(String s : second) newSecond.add("0"+s);
            for(String s : second) newSecond.add("1"+s);
            for(String s : second) newSecond.add("8"+s);
            for(String s : second) newSecond.add("9"+s);
            for(String s : second) newSecond.add("6"+s);
            
            List<List<String>> both = new ArrayList<List<String>>();
            both.add(newFirst);
            both.add(newSecond);
            return both;
            
        }
    }

Log in to reply
 

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