Java fast backtracking solution beat 7ms


  • 0
    L
    public class Solution {
        public List<String> findStrobogrammatic(int n) {
            String[] numbers = new String[]{"00", "11", "88", "69", "96"};
            List<String> res = new ArrayList<>();
            helper(res, numbers, new char[n], 0);
            return res;
        }
        
        public void helper(List<String> res, String[] numbers, char[] chars, int pos) {
            
            if (pos == Math.ceil(chars.length/2.0)) {
                res.add(new String(chars));
                return;
            }
            
            for (int i = 0; i < numbers.length; i++) {
                if (chars.length > 1 && pos == 0 && i == 0) continue; // except n == 1, the outest layer should not be 0xxx0 
                if (i > 2 && pos == chars.length / 2) break;            // n is odd, the mid number can only be 0, 1, 8   no need to worry about n is even
                chars[pos] = numbers[i].charAt(0);
                chars[chars.length- 1 - pos] = numbers[i].charAt(1);
                helper(res, numbers, chars, pos+1);
            }
            
        }
        
    }
    

Log in to reply
 

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