7 ms Java short recursive ( > 93.80% solutions)

  • 3
    char[][] dict = new char[][] {{'0','0'},{'1','1'},{'6','9'},{'8','8'},{'9','6'}};
    public List<String> findStrobogrammatic(int n) {
        List<String> res = new ArrayList<>();
        char[] sofar = new char[n];
        findS(n, n, 0, sofar, res);
        return res;
    private void findS(int n, int m, int j, char[] soFar, List<String> res) {
        if (m <= 0) { res.add(new String(soFar)); return; }
        for (int i = 0; i < dict.length; i++) {
            if ((m == 1 && ( dict[i][0] == '6' || dict[i][0] == '9' )) ||
               (m > 1 && j == 0 && dict[i][0] == '0')) continue;
            soFar[j] = dict[i][0];
            soFar[n-j-1] = dict[i][1];
            findS(n, m-2, j+1, soFar, res);

  • 0

    This solution like the concatenation solution, is still O(n*4^n). However, it do save a lot of operations compared to the classical concatenation method.

  • 0

    The time complexity is the same. In fact, I would be surprised if someone came up with a better complexity for a permutation problem where we have to list all permutations. So I tried to optimize it elsewhere, i.e. space complexity and a bit of performance. I generally think it's a good approach to use fixed sized arrays where possible. It looks much cleaner than Objects, StringBuilders etc. and has better performance. Java folk like me are too used to using Java libraries, it's sometimes useful to take inspiration from C and explicit memory management.

Log in to reply

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