We use a mobile numeric keyboard. 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 (* and #). Given a number, find out the number of possible numbers combinations of the given length.
Input: int input = 2; Output: 36 Explanation: Possible numbers are (00,08), (11,12,14), (22,21,23,25)… |
Solution:
1. static int getCountOfPossibleNumbers(char[][] keypad, int length) { 2. if (keypad == null || length <= 0) { 3. return 0; 4. } 5. if (length == 1) { 6. return 10; 7. } 8. 9. int[] rowMoves = {0, 0, -1, 0, 1}; 10. int[] columnMoves = {0, -1, 0, 1, 0}; 11. int[][] count = new int[10][length + 1]; 12. 13. for (int i = 0; i <= 9; i++) { 14. count[i][0] = 0; 15. count[i][1] = 1; 16. } 17. 18. for (int k = 2; k <= length; k++) { 19. for (int keypadRow = 0; keypadRow < 4; keypadRow++) { 20. for (int keypadColumn = 0; keypadColumn < 3; keypadColumn++) { 21. if (keypad[keypadRow][keypadColumn] != '*' && keypad[keypadRow][keypadColumn] != '#') { 22. int num = keypad[keypadRow][keypadColumn] - '0'; 23. count[num][k] = 0; 24. for (int move = 0; move < 5; move++) { 25. int row = keypadRow + rowMoves[move]; 26. int column = keypadColumn + columnMoves[move]; 27. if (row >= 0 && row <= 3 && column >= 0 && column <= 2 && keypad[row][column] != '*' && keypad[row][column] != '#') { 28. int nextNumber = keypad[row][column] - '0'; 29. count[num][k] += count[nextNumber][k - 1]; 30. } 31. } 32. } 33. } 34. } 35. } 36. 37. int totalCount = 0; 38. for (int i = 0; i <= 9; i++) { 39. totalCount += count[i][length]; 40. } 41. return totalCount; 42. } 43.