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

Using Iterative 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).

JavaScript

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)

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)