Longest Path With Different Adjacent Characters - Leetcode Solution

Problem Statement:

Given a matrix of lower alphabets and a dictionary. Find the longest path in the matrix such that all the characters in the path are different and the path is a valid word in the dictionary. The path can only be created using adjacent cells in 4 directions (Up, Down, Left, Right).

Solution: The problem is solvable using a simple DFS algorithm. We traverse the matrix, for every cell in the matrix, we start a DFS traversal in all the 4 directions. We maintain a set to keep track of the characters we have already encountered. If a character is already in the set, we discard that traversal branch because we want all the characters to be different on the path. We also check if the constructed path is a valid word in the dictionary. If the path is a valid word and is longer than the current max-length path, we update the max-length path.

Algorithm:

1. Create a visited set to keep track of the visited nodes.
2. Initialize the max-length path to 0
3. Traverse the matrix, for every cell in the matrix.
4. Start a DFS traversal in all 4 directions. To avoid visiting the same node multiple times, we add the cell to the visited set before starting the DFS traversal.
5. Before traversing to a neighbor, we add the character on the current cell to a set used_chars
6. If a character is already in used_chars, we discard that traversal branch.
7. If the constructed path is a valid word in the dictionary, we update the max-length path.
8. After traversing all neighbors, we remove the character from used_chars set.
9. Remove the current cell from the visited set.

Code:

Here's the implementation of the above algorithm:

def dfs(matrix, row, col, visited, used_chars, dictionary, max_len):
    visited.add((row, col)) # mark the current cell as visited
    used_chars.add(matrix[row][col]) # add the current character to used_chars set
    path = "".join(used_chars) # construct the path
    if len(path) > max_len and path in dictionary: # check if path is a valid word and is longer than the current max-length path
        max_len = len(path)
    
    for dr, dc in [(0, 1), (1, 0), (-1, 0), (0, -1)]: # traverse all 4 neighbors
        r, c = row + dr, col + dc
        if r >= 0 and r < len(matrix) and c >= 0 and c < len(matrix[0]) and (r, c) not in visited:
            # traverse only if the cell is within the boundaries of the matrix, not already visited 
            # and not equal to the character already present in used_chars set
            if matrix[r][c] not in used_chars:
                max_len = dfs(matrix, r, c, visited, used_chars, dictionary, max_len)
    used_chars.remove(matrix[row][col]) # remove the current character from used_chars set
    visited.remove((row, col)) # remove the current cell from visited set
    return max_len


def longestPath(matrix, dictionary):
    # traverse the matrix, for every cell in the matrix.
    max_len = 0
    visited = set()
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            used_chars = set()
            # start a DFS traversal in all 4 directions. 
            #To avoid visiting the same node multiple times, 
            # we add the cell to the visited set before starting the DFS traversal.
            if (i, j) not in visited:
                max_len = dfs(matrix, i, j, visited, used_chars, dictionary, max_len)
    return max_len

Time Complexity: The time complexity of the above solution is O(4^(n*m)) where n and m are the dimensions of the matrix. In the worst case, all possible paths with all different characters will be checked.

Space Complexity: The space complexity of the above solution is O(n*m) for the visited set and used_chars set. In the worst case, all cells are visited.

1