JavaScript Program to Print all Palindromic Paths from Top Left to Bottom Right in a Matrix
We are given a matrix containing only lower-case alphabetical characters. The task is to print all the palindromic paths present in the given matrix. A path is a sequence of cells starting from the top-left cell and ending at the bottom-right cell. We are allowed to move only to the right and down from the current cell. We cannot go down diagonally.
Example:
Input : mat[][] = {"aaab”,
"baaa”
“abba”}
Output: aaaaaa, aaaaaa, abaaba
Explanation :
aaaaaa (0, 0) -> (0, 1) -> (1, 1) ->
(1, 2) -> (1, 3) -> (2, 3)
aaaaaa (0, 0) -> (0, 1) -> (0, 2) ->
(1, 2) -> (1, 3) -> (2, 3)
abaaba (0, 0) -> (1, 0) -> (1, 1) ->
(1, 2) -> (2, 2) -> (2, 3)
Note: The order of elements in the output array doesn’t matter.
Table of Content
- Using Recursive Depth-First Search (DFS)
- Using Iterative Depth-First Search (DFS)
Using Recursive Depth-First Search (DFS)
In this approach, we employ recursive DFS to traverse the matrix, exploring all possible paths from the top-left corner to the bottom-right corner. We extend the current path by moving right or down at each step, checking if the characters along the path form a palindrome. If they do, we add the path to the list of palindromic paths.
Approach:
- Define a recursive function to perform DFS traversal from the top-left corner to the bottom-right corner of the matrix.
- Extend the current path by moving right or down.
- Check if the characters along the path form a palindrome.
- If the path is a palindrome, add it to the list of palindromic paths.
- Recursively explore further paths until reaching the bottom-right corner.
Example: Implementation of program to print all palindromic paths from top left to bottom right in a matrix using Recursive Depth-First Search (DFS).
const palindromicPaths = (matrix) => {
const m = matrix.length;
const n = matrix[0].length;
const result = [];
const dfs = (i, j, path) => {
path += matrix[i][j];
if (i === m - 1 && j === n - 1) {
if (isPalindrome(path)) {
result.push(path);
}
return;
}
if (j + 1 < n) {
dfs(i, j + 1, path);
}
if (i + 1 < m) {
dfs(i + 1, j, path);
}
};
const isPalindrome = (str) => {
return str === str.split('').reverse().join('');
};
dfs(0, 0, '');
return result;
};
const matrix = [
['a', 'a', 'a', 'b'],
['b', 'a', 'a', 'a'],
['a', 'b', 'b', 'a']
];
console.log(palindromicPaths(matrix));
Output
[ 'aaaaaa', 'aaaaaa', 'abaaba' ]
Time Complexity: O(2^(m+n)) , where m is the number of rows and n is the number of columns in the matrix.
Auxiliary Space: O(m+n)
Using Iterative Depth-First Search (DFS)
In this approach, we utilize an iterative DFS to traverse the matrix, exploring all possible paths from the top-left corner to the bottom-right corner. We maintain a stack to keep track of the current path. At each step, we extend the current path by moving right or down and check if the characters along the path form a palindrome. If they do, we add the path to the list of palindromic paths.
Approach:
- Initialize a stack with the starting cell (top-left corner) of the matrix.
- While the stack is not empty, pop a cell from the stack.
- Extend the current path by moving right or down from the popped cell.
- Check if the characters along the path form a palindrome.
- If the path is a palindrome, add it to the list of palindromic paths.
- Push the extended paths onto the stack.
- Continue until reaching the bottom-right corner of the matrix.
Example: Implementation of program to print all palindromic paths from top left to bottom right in a matrix using Iterative Depth-First Search (DFS)
const palindromicPathsDP = (matrix) => {
const m = matrix.length;
const n = matrix[0].length;
const dp = Array.from({ length: m },
() => Array.from({ length: n }, () => []));
dp[0][0].push(matrix[0][0]);
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i === 0 && j === 0) continue;
if (i > 0) {
dp[i - 1][j].forEach(path => {
dp[i][j].push(path + matrix[i][j]);
});
}
if (j > 0) {
dp[i][j - 1].forEach(path => {
dp[i][j].push(path + matrix[i][j]);
});
}
}
}
const isPalindrome = (str) => {
let left = 0;
let right = str.length - 1;
while (left < right) {
if (str[left] !== str[right]) return false;
left++;
right--;
}
return true;
};
const allPaths = dp[m - 1][n - 1];
const palindromicPaths =
allPaths.filter(path => isPalindrome(path));
return palindromicPaths;
};
const matrix = [
['a', 'a', 'a', 'b'],
['b', 'a', 'a', 'a'],
['a', 'b', 'b', 'a']
];
console.log(palindromicPathsDP(matrix));
Output
[ 'aaaaaa', 'aaaaaa', 'abaaba' ]
Time Complexity: O(2^(m+n)),where m is the number of rows and n is the number of columns in the matrix.
Auxiliary Space: O(m+n)
Contact Us