Share my clean and fast Java solution


  • 0
    L
    class Solution {
        public List<String> findStrobogrammatic(int n) {
            List<String> res = new ArrayList<>();
            char[] chars = new char[n];
            Map<Character, Character> map = new HashMap<>();
            map.put('0', '0');
            map.put('1', '1');
            map.put('8', '8');
            map.put('6', '9');
            map.put('9', '6');
            helper(chars, 0, n-1, map, res);
            return res;
        }
        
        private void helper(char[] chars, int lo, int hi, Map<Character, Character> map, List<String> res) {
            if (lo > hi) {
                res.add(new String(chars));
                return;
            }
            
            for (Map.Entry<Character, Character> entry : map.entrySet()) {
                // the mid digit cannot be 6 or 9 e.g 161, 090, etc. are not allowed.
                if (lo == hi && (entry.getKey() == '6' || entry.getKey() == '9')) continue;
                // remove the leading zero cases except the one digit case: 0 
                if (lo < hi && lo == 0 && entry.getKey() == '0') continue;
                
                chars[lo] = entry.getKey();
                chars[hi] = entry.getValue();
                helper(chars, lo+1, hi-1, map, res);
            }
        }
    }
    

Log in to reply
 

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