Given a matrix of characters, find the length of the longest path starting from a character, in such a way that the characters are arranged in alphabetical order. You can mode in any direction from a cell.
Input: char character = 'a'; char[][] mat = {{'a', 'c', 'd'}, {'h', 'b', 'a'}, {'i', 'g', 'f'}}; Output: 4 Explanation: The longest consecutive path starting from a is: a, b, c, d. |
Solution:
1. static int[] x = {0, 1, 1, -1, 1, 0, -1, -1}; 2. static int[] y = {1, 0, 1, 1, -1, -1, 0, -1}; 3. static int ROWS = 3; 4. static int COLUMNS = 3; 5. 6. static int[][] consecutivePaths = new int[ROWS][COLUMNS]; 7. 8. static boolean isValidCell(int row, int column) { 9. return row >= 0 && column >= 0 && row < ROWS && column < COLUMNS; 10. } 11. 12. static boolean isAdjacentCharacter(char previous, char current) { 13. return ((current - previous) == 1); 14. } 15. 16. static int getLength(char[][] characters, int row, int column, char previous) { 17. 18. if (!isValidCell(row, column) || !isAdjacentCharacter(previous, characters[row][column])) { 19. return 0; 20. } 21. 22. if (consecutivePaths[row][column] != -1) { 23. return consecutivePaths[row][column]; 24. } 25. 26. int longestPath = 0; 27. for (int i = 0; i < 8; i++) { 28. longestPath = Math.max(longestPath, 1 + getLength(characters, row + x[i], column + y[i], characters[row][column])); 29. } 30. return consecutivePaths[row][column] = longestPath; 31. } 32. 33. static int getConsecutivePathLength(char[][] characters, char character) { 34. for (int i = 0; i < ROWS; ++i) { 35. for (int j = 0; j < COLUMNS; ++j) { 36. consecutivePaths[i][j] = -1; 37. } 38. } 39. 40. int longestPath = 0; 41. for (int row = 0; row < ROWS; row++) { 42. for (int column = 0; column < COLUMNS; column++) { 43. if (characters[row][column] == character) { 44. for (int i = 0; i < 8; i++) { 45. longestPath = Math.max(longestPath, 1 + getLength(characters, row + x[i], column + y[i], character)); 46. } 47. } 48. } 49. } 50. return longestPath; 51. }