Fast Java solution (5 ms), recursion


  • 0
    J
    public class Solution {
        static char[] map = {'0', '1', 'x', 'x', 'x', 'x', '9', 'x', '8', '6'};
        static char[] set = {'0', '1', '6', '8', '9'};
        static char[] setOdd = {'0', '1', '8'};
        
        public List<String> findStrobogrammatic(int n) {
            List<String> output = new ArrayList<>();
            char[] buffer = new char[n];
            solve(output, buffer, n, 0); // start with filling the 0th element
            return output;
        }
        
        void solve(List<String> output, char[] buffer, int n, int i) {
            int limit = (n % 2 == 0) ? n / 2 : n / 2 + 1;
            if (i >= limit) {
                if (n == 1 || buffer[0] != '0') output.add(new String(buffer));
                return;
            }
            char[] chars = (i == n / 2) ? setOdd : set;
            for (char c : chars) {
                buffer[i] = c;
                buffer[n - 1 - i] = map[c - '0'];
                solve(output, buffer, n, i + 1);
            }
        }
    }

Log in to reply
 

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