README.md

🔍 Word Search (Up/Down/Left/Right Only)

This project is a simple implementation of a Word Search solver that checks whether a given word exists in a 2D grid (matrix) of letters.

✅ Traversal is allowed only in the four cardinal directions:

• Up
• Down
• Left
• Right

❌ Diagonal moves are not allowed.

❗ Words must be formed using consecutive letters, i.e., each letter in the word must be adjacent to the previous one.

---

🚀 Example

Board:

### 📋 Example Board

A  B  C  D  
E  F  G  H  
I  J  K  L  
M  N  O  P

Word: "FINE"

✅ Output: true (Path: F → I → N → E)

---

🧠 Approach

The solution uses Depth-First Search (DFS) recursively to:

• Start from each cell in the grid
• Check if the word can be constructed by moving up, down, left, or right step by step
• Track visited positions to avoid revisiting

---

📊 Time & Space Complexity

⏱️ Time Complexity: O(N * M * 4^L)

Where:

• N is the number of rows in the board
• M is the number of columns
• L is the length of the word being searched

Why?

• In the worst case, we start DFS from every cell (N * M)
• From each cell, we can explore up to 4 directions (4^L combinations in the depth of recursion for word of length L)

---

🧠 Auxiliary Space Complexity: O(L)

• The recursion depth goes up to the length of the word L
• Additionally, we use a visited[][] matrix of size N x M (can also be reused)

So the total auxiliary space is:

• O(L) for recursion stack
• O(N*M) for the visited matrix (if not modifying the board in place) .