How to use Iterative Depth-First Search (DFS) In Javascript
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)
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)
Contact Us