How to use Iterative Depth-First Search (DFS) In Javascript

Using Recursive 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)

JavaScript

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)