Simple java dfs


  • 0
    V
        List<String> toRet;
        HashMap<Character, Character> hm;
        public List<String> findStrobogrammatic(int n)
        {
            if(n == 1)
                return new ArrayList<String>(){{add("0");add("1");add("8");}};
            toRet = new ArrayList<String>();
            hm = new HashMap<Character, Character>();
            hm.put('0', '0');hm.put('1', '1');hm.put('6','9');hm.put('9','6');hm.put('8','8');
            char[] arr = new char[n];
            dfs(arr, 0, n);
            return toRet;
        }
        void dfs(char[] arr, int ind, int len)
        {
            if(ind == (len + 1) / 2)
            {
                toRet.add(new String(arr));
                return;
            }
            for(char k: hm.keySet())
            {
                if(ind == 0 && k == '0' || ind == len / 2 && (k == '9' || k == '6'))
                    continue;
                arr[ind] = k;
                arr[len - 1 - ind] = hm.get(k);
                dfs(arr, ind + 1, len);
            }
        }

Log in to reply
 

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