Word Search in Grid 🎯

Welcome to the exciting world of Data Structures and Algorithms! Today, we're going to dive into a fun problem - Word Search in Grid. This is a common problem in programming that you'll encounter in many real-world projects.

Understanding the Problem 📝

Given a 2D grid (a matrix) and a list of words, the goal is to find all the words in the grid. Each word is composed of lowercase letters and the grid contains only lowercase letters as well. Words can appear horizontally or vertically, and they can even wrap across rows or columns.

Breaking Down the Solution 💡

To solve this problem, we'll implement a simple depth-first search (DFS) algorithm. DFS is a common algorithm used for traversing or searching tree or graph structures, and it's perfect for our grid-based word search.

DFS Algorithm Explanation 💡

Start from a given cell in the grid.
Explore all the neighboring cells and check if the current word can be formed by concatenating the letters in the visited cells.
If the word is found, mark it as visited to avoid revisiting it.
If all neighboring cells have been checked and the word isn't found, backtrack to the previous cell and continue the search with the next unvisited neighbor.
Repeat the process until all words in the list have been found or all cells in the grid have been checked.

Implementing the Solution 💡

Let's write some code to implement this solution! We'll define a helper function, searchWords, which takes the grid, list of words, and starting cell coordinates as input.

python

def searchWords(grid, words, start_x, start_y):
    # Define visited cells
    visited = set()

    def dfs(x, y, word):
        # Base case: if word is empty, we've found a word
        if not word:
            return True

        # Check all neighboring cells
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            new_x, new_y = x + dx, y + dy

            # If the cell is out of bounds or already visited, skip it
            if not (0 <= new_x < len(grid) and 0 <= new_y < len(grid[0])) or (new_x, new_y) in visited:
                continue

            # If the cell's content matches the current letter, proceed with DFS
            if grid[new_x][new_y] == word[0]:
                visited.add((new_x, new_y))

                # Recursively search the rest of the word
                if dfs(new_x, new_y, word[1:]):
                    return True

                # Backtrack if the word isn't found
                visited.remove((new_x, new_y))

    # Start the DFS search from the starting cell
    visited.add((start_x, start_y))
    for word in words:
        if dfs(start_x, start_y, word):
            print(word)

Putting It All Together 💡

To test our implementation, let's create a sample grid and list of words:

python

grid = [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E'],
]

words = ['ABC', 'CDE', 'AFE']

# Call the searchWords function
searchWords(grid, words, 0, 0)

When you run this code, you should see the found words printed out.

Challenge Time 🎯

Now that you've seen how to implement the Word Search in Grid problem, try modifying the searchWords function to handle words that can wrap across rows and columns.

That's all for today! By now, you should have a solid understanding of how to approach and solve the Word Search in Grid problem using a depth-first search algorithm. Keep practicing, and you'll be a master of Data Structures and Algorithms in no time! 🚀