Java DFS version


  • 0
    I
    class Solution {
        public List<String> findStrobogrammatic(int n) {
            List<String> result = new ArrayList<>();
            if(n <= 0) return result;
            Map<Character,Character> allmap = new HashMap<>();
            allmap.put('1','1');
            allmap.put('0','0');
            allmap.put('8','8');
            allmap.put('6','9');
            allmap.put('9','6');
            Map<Character,Character> somemap = new HashMap<>();
            somemap.put('1','1');
            somemap.put('0','0');
            somemap.put('8','8');
            char[] temp = new char[n];
            
            helper(result,allmap,somemap,0,n-1,temp);
            return result;
        }
        private void helper(List<String> result, Map<Character,Character> allmap,Map<Character,Character> somemap, int left, int right,char[] temp){
            if(left > right){
                if(temp[0] != '0')
                result.add(new String(temp));
                return;
            }
            if(left == right){
                if(temp.length == 1 || temp[0] != '0')
                    for(char i : somemap.keySet()){
                        temp[left] = i;
                        result.add(new String(temp));
                    }
                return;
            }
            for(char i : allmap.keySet()){
                temp[left] = i;
                temp[right] = allmap.get(i);
                helper(result,allmap,somemap,left+1,right-1,temp);
            }
        }
    }
    

Log in to reply
 

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