My Concise JAVA Solution using DFS


  • 11
    S
    public class Solution {
        public List<String> findStrobogrammatic(int n) {
            Map<Character, Character> map = new HashMap<Character, Character>();
            map.put('0', '0');
            map.put('1', '1');
            map.put('6', '9');
            map.put('8', '8');
            map.put('9', '6');
            List<String> result = new ArrayList<String>();
            char[] buffer = new char[n];
            dfs(n, 0, buffer, result, map);
            return result;
        }
        
        private void dfs(int n, int index, char[] buffer, List<String> result, Map<Character, Character> map) {
            if (n == 0) {
                return;
            }
            if (index == (n + 1) / 2) {
                result.add(String.valueOf(buffer));
                return;
            }
            for (Character c : map.keySet()) {
                if (index == 0 && n > 1 && c == '0') {  // first digit cannot be '0' when n > 1
                    continue;
                }
                if (index == n / 2 && (c == '6' || c == '9')) {   // mid digit cannot be '6' or '9' when n is odd
                    continue;
                }
                buffer[index] = c;
                buffer[n - 1 - index] = map.get(c);
                dfs(n, index + 1, buffer, result, map);
            }
        }
    }

  • 0

    why it does not need backtracking after dfs(n, index + 1, buffer, result, map);
    like remove a char in the buffer??


  • 0
    W

    Because he noticed that the buffer would be fixed size in n. So he use an array instead. The old value would got overwritten at next time.


  • 1

    Great solution. First I was trying to use StringBuilder. But it is hard to append on both sides. char[] is much more better.


  • 0
    A

    is the runtime O(n)?


Log in to reply
 

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