Mobile Numeric Keypad Problem

Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the current button. You are not allowed to press bottom row corner buttons (i.e. * and # ).

Given a number N, find out the number of possible numbers of given length.

Mobile-keypad

Examples: For N=1, number of possible numbers would be 10 (0, 1, 2, 3, …., 9) For N=2, number of possible numbers would be 36 Possible numbers: 00,08 11,12,14 22,21,23,25 and so on. If we start with 0, valid numbers will be 00, 08 (count: 2) If we start with 1, valid numbers will be 11, 12, 14 (count: 3) If we start with 2, valid numbers will be 22, 21, 23,25 (count: 4) If we start with 3, valid numbers will be 33, 32, 36 (count: 3) If we start with 4, valid numbers will be 44,41,45,47 (count: 4) If we start with 5, valid numbers will be 55,54,52,56,58 (count: 5) ……………………………… ………………………………

We need to print the count of possible numbers.

class Solution {
    public static int helper(int[][] dp, char[][] keypad, int i, int j) {
        if (i >= 0 && i < 4 && j >= 0 && j < 3 && keypad[i][j] != '*' && keypad[i][j] != '#')
            return dp[i][j];
        return 0;
    }

    public static int getCount(char[][] keypad, int N) {
        int[][] dp = new int[4][3];
        // base case when n=1
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 3; j++) {
                if (keypad[i][j] != '*' && keypad[i][j] != '#')
                    dp[i][j] = 1;
            }
        }
        for (int n = 2; n <= N; n++) {
            int[][] copy = new int[4][3];
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 3; j++) {
                    if (keypad[i][j] != '*' && keypad[i][j] != '#') {
                        copy[i][j] = dp[i][j];
                        copy[i][j] += helper(dp, keypad, i + 1, j);
                        copy[i][j] += helper(dp, keypad, i, j + 1);
                        copy[i][j] += helper(dp, keypad, i - 1, j);
                        copy[i][j] += helper(dp, keypad, i, j - 1);
                    }
                }
            }
            dp = copy;
        }
        int ans = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 3; j++)
                ans += dp[i][j];
        }
        return ans;
    }
}