Word Search in a Straight Line

Here is the full interview question "Word Search in a Straight Line - Uber Coding Interview | ShowOffer" from Uber on ShowOffer.io:

Problem Statement: Given a 2D grid of characters and a dictionary of words, find all the words in the dictionary that exist in the grid. Words can be constructed by moving from one cell to an adjacent cell (up, down, left, or right), but you cannot move diagonally. Additionally, each cell in the grid can be visited at most once in a word.

Examples:

1. Grid: [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] Dictionary: ['ABCE', 'SEE', 'ABCB'] Output: ['ABCE', 'SEE']

2. Grid: [ ['t','y'], ['t','y'] ] Dictionary: ['tt', 'yy', 'tty', 'tyty'] Output: ['tty', 'tyty']

Constraints:

• 1 <= grid.length <= 500
• 1 <= grid[0].length <= 500
• 1 <= dictionary.length <= 500
• 1 <= dictionary[i].length <= 10
• All words are composed of English letters.

Hints:

1. Use depth-first search (DFS) to explore all possible paths in the grid.
2. Keep track of visited cells to avoid revisiting them within the same word.

Solution: `python def exist(board, words): def dfs(i, j, word): if len(word) == 0: return True if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[0]: return False temp, board[i][j] = board[i][j], '/' found = (dfs(i + 1, j, word[1:]) or dfs(i - 1, j, word[1:]) or dfs(i, j + 1, word[1:]) or dfs(i, j - 1, word[1:])) board[i][j] = temp return found

for word in words:
    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(i, j, word):
                return True
return False

`

This solution uses DFS to explore all possible paths in the grid and checks if any word in the dictionary exists. It keeps track of visited cells by temporarily replacing them with '/' and restoring the original value after the DFS call returns. If any word is found, the function returns True; otherwise, it returns False.

The time complexity is O(N^2 * M^3), where N is the number of rows in the grid and M is the maximum length of a word in the dictionary. The space complexity is O(M) for the recursion stack.