4ms Java recursion solution


  • 1
    M
    public class Solution {
        public List<String> findStrobogrammatic(int n) {
            char[] k = new char[] {'0', '1', '8', '6', '9'};
            char[] v = new char[] {'0', '1', '8', '9', '6'};
            List<String> res = new ArrayList<>();
            char[] buf = new char[n];
            find(k, v, res, buf, 0, n);
            return res;
        }
        
        private void find(char[] k, char[] v, List<String> res, char[] buf, int idx, int n) {
            if (idx > n / 2 || (idx == n / 2 && n % 2 == 0)) {
                res.add(new String(buf));
                return;
            }
            for (int i = 0; i < k.length; i++) {
                if ((idx == 0 && k[i] == '0' && n > 1)
                    || (idx == n - idx - 1 && (k[i] == '6' || k[i] == '9'))) {
                    continue;
                }
                
                buf[idx] = k[i];
                buf[n - idx - 1] = v[i];
                find(k, v, res, buf, idx + 1, n);
            }
        }
    }

Log in to reply
 

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