- Notifications
You must be signed in to change notification settings - Fork180
added new algorithm named Word Search in Simple Recursive Algorithms.#42
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Open
hrushi2003 wants to merge1 commit intoalgorithm-visualizer:masterChoose a base branch
base:master
Could not load branches
Branch not found:{{ refName }}
Loading
Could not load tags
Nothing to show
Loading
Are you sure you want to change the base?
Some commits from the old base branch may be removed from the timeline, and old review comments may become outdated.
Uh oh!
There was an error while loading.Please reload this page.
Open
Changes fromall commits
Commits
File filter
Filter by extension
Conversations
Failed to load comments.
Loading
Uh oh!
There was an error while loading.Please reload this page.
Jump to
Jump to file
Failed to load files.
Loading
Uh oh!
There was an error while loading.Please reload this page.
Diff view
Diff view
There are no files selected for viewing
63 changes: 63 additions & 0 deletionsSimple Recursive/Word Search/README.md
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,63 @@ | ||
| # 🔍 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: | ||
| <pre> | ||
| ### 📋 Example Board | ||
| A B C D | ||
| E F G H | ||
| I J K L | ||
| M N O P | ||
| </pre> | ||
| ### 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) . |
119 changes: 119 additions & 0 deletionsSimple Recursive/Word Search/code.js
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,119 @@ | ||
| // import visualization libraries { | ||
| const { Array2DTracer,Array1DTracer, Layout, LogTracer, Tracer, VerticalLayout } = require('algorithm-visualizer'); | ||
| // } | ||
| const N = 4; // just change the value of N and the visuals will reflect the configuration! | ||
| const board = [ | ||
| ['A','L','U','C'], | ||
| ['E','F','L','U'], | ||
| ['X','I','N','C'], | ||
| ['Q','Y','E','K'] | ||
| ]; | ||
| const word = ['L','U','C','K']; | ||
| // define tracer variables { | ||
| const boardTracer = new Array2DTracer('Board'); | ||
| const logger = new LogTracer('Progress'); | ||
| const wordTracer = new Array1DTracer('Word'); | ||
| Layout.setRoot(new VerticalLayout([boardTracer,wordTracer,logger])); | ||
| boardTracer.set(board); | ||
| wordTracer.set(word); | ||
| logger.println(`board of size ${N} X ${N} consisting of letters`); | ||
| Tracer.delay() | ||
| // } | ||
| function wordSearch(board,word,r,c,indx){ | ||
| let rowBounds = r >= 0 && r < board.length; | ||
| let colBounds = c >= 0 && c < board.length; | ||
| if(!rowBounds){ | ||
| // logger { | ||
| logger.println("The current position is out of bounds"); | ||
| // } | ||
| return false; | ||
| } | ||
| if(!colBounds){ | ||
| // logger { | ||
| logger.println("The current position is out of bounds"); | ||
| // } | ||
| return false; | ||
| } | ||
| if(board[r][c] == '#'){ | ||
| // logger { | ||
| logger.println(`The current position ${r} and ${c} is already visited`); | ||
| // } | ||
| return false; | ||
| } | ||
| if(indx == word.length){ | ||
| // logger { | ||
| logger.println("The given word is found"); | ||
| // } | ||
| return true; | ||
| } | ||
| // visualize { | ||
| boardTracer.select(r, c); | ||
| wordTracer.select(indx); | ||
| Tracer.delay(); | ||
| logger.println(`Trying matching word ${word[indx]} at row ${r} & col ${c}`); | ||
| // } | ||
| if(board[r][c] == word[indx]){ | ||
| let temp = board[r][c]; | ||
| board[r][c] = '#'; | ||
| // visualize { | ||
| boardTracer.patch(r,c,temp); | ||
| Tracer.delay(); | ||
| // } | ||
| let isFound = false; | ||
| isFound = isFound || wordSearch(board,word,r + 1,c,indx + 1); | ||
| isFound = isFound || wordSearch(board,word,r - 1,c,indx + 1); | ||
| isFound = isFound || wordSearch(board,word,r,c + 1,indx + 1); | ||
| isFound = isFound || wordSearch(board,word,r,c - 1,indx + 1); | ||
| if(isFound){ | ||
| return true; | ||
| } | ||
| // visualize { | ||
| boardTracer.deselect(r, c); | ||
| Tracer.delay(); | ||
| logger.println(`row ${r} & col ${c} didn't work out`); | ||
| // } | ||
| board[r][c] = temp; | ||
| // visualize { | ||
| boardTracer.deselect(r,c); | ||
| wordTracer.deselect(indx); | ||
| boardTracer.depatch(r,c); | ||
| Tracer.delay(); | ||
| // } | ||
| } | ||
| // visualize { | ||
| boardTracer.deselect(r,c); | ||
| wordTracer.deselect(indx); | ||
| Tracer.delay(); | ||
| // } | ||
| return false; | ||
| } | ||
| function main(){ | ||
| for(let i = 0; i < N; i++){ | ||
| for(let j = 0; j < N; j++){ | ||
| // visualize { | ||
| wordTracer.select(0); | ||
| boardTracer.select(i,j); | ||
| Tracer.delay(); | ||
| // } | ||
| if(board[i][j] == word[0]){ | ||
| // logger { | ||
| logger.println(`The letter ${word[0]} is matched and the function is going to run to traverse and find the remaining letters to form target word`); | ||
| // } | ||
| if(wordSearch(board,word,i,j,0)){ | ||
| return true; | ||
| } | ||
| } | ||
| // visualize { | ||
| wordTracer.deselect(0); | ||
| boardTracer.deselect(i,j); | ||
| Tracer.delay(); | ||
| // } | ||
| } | ||
| } | ||
| return false; | ||
| } | ||
| main(); |
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.