A Java solution without recursion


  • 0
    H
    public List<String> findStrobogrammatic(int n) {
        if (n <= 0) return new ArrayList<String>();
        if (n == 1) return new ArrayList<String>(Arrays.asList("0", "1", "8"));
        List<String> result = new ArrayList<String>(Arrays.asList(""));
        for (int i = 0; i < (n + 1) / 2; ++i) {
            List<String> nex = new ArrayList<String>();
            for (String s : result) {
                if (i != 0) nex.add(s + "0");
                nex.add(s + "1");
                if (n % 2 == 0 || i != (n + 1) / 2 - 1) nex.add(s + "6");
                nex.add(s + "8");
                if (n % 2 == 0 || i != (n + 1) / 2 - 1) nex.add(s + "9");
            }
            result = nex;
        }
        
        List<String> finalResult = new ArrayList<String>();        
        for (String s : result) {
            StringBuilder tmp = new StringBuilder();
            for (int i = 0; i < n / 2; ++i) {
                char c = s.charAt(i);
                if (c == '6') {
                    tmp.insert(0, '9');
                } else if (c == '9') {
                    tmp.insert(0, '6');
                } else {
                    tmp.insert(0, c);
                }
            }
            tmp.insert(0, s);
            finalResult.add(tmp.toString());
        }
        return finalResult;
    }

Log in to reply
 

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