Java fast char array two pointer solution


  • 1
    A

    I tried to solve this problem using two pointers for the current left and right position respectively and the space is reused by filling one char array. The algorithm should be straightforward.

    char[][] pair = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'} , {'9', '6'}};
    char[] single = {'0', '1', '8'};
    
    public List<String> findStrobogrammatic(int n) {
        List<String> res = new ArrayList<>();
        if (n <= 0) return res;
        char[] arr = new char[n];
        construct(arr, 0, n -1, res);
        return res;
    }
    
    private void construct(char[] arr, int i, int j, List<String> res) {
        if (i > j) {
            res.add(String.valueOf(arr));
        } else if (i == j) {
            int idx = 0;
            while (idx < single.length) {
                arr[i] = single[idx++];
                res.add(String.valueOf(arr));
            }
        } else {
            int idx = i == 0 ? 1 : 0;
            while (idx < pair.length) {
                arr[i] = pair[idx][0];
                arr[j] = pair[idx][1];
                construct(arr, i + 1, j - 1, res);
                idx++;
            }
        }
    }

  • 0

    This method is super fast. Thank you for the sharing.:)


Log in to reply
 

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