Multiple Word Searching Algorithm














































Multiple Word Searching Algorithm



In this article we are going to write the function that helps in find all the words present in a given2-D matrix.

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

 

Example:

Input: 
board = [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

 

Note:

  1. All inputs are consist of lowercase letters a-z.
  2. The values of words are distinct.
We are only concerned about the function inside the solution class. Other functions are for pre-processing the inputs to handle all cases. 


class Solution {
public:
string myword;
int row,col;
vector<vector<char>>bv;
bool vis[201][201]={false};
bool findword(int rw,int cl,int ind)
{
int sz=ind,slen=myword.length();
if(rw>=row||cl>=col)return false;
if(sz==slen)return true;
bool flag1=false,flag2=false,flag3=false,flag4=false,flag5=false;
if(sz==0){
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++){
if(bv[i][j]==myword[0]){
vis[i][j]=true;
flag1=findword(i,j,ind+1);
vis[i][j]=false;
if(flag1)return true;
}
}
}
}
int curcl,currw,prcl,prrw;
curcl=(cl+1);
currw=(rw+1);
prcl=cl-1;
prrw=rw-1;
// cout<<"cur row "<<currw<<" cur col "<<curcl<<" prev row "<<prrw<<" prev col "<<prcl<<endl;
if(curcl<col&&bv[rw][curcl]==myword[ind]&& vis[rw][curcl]==false){
// cout<<"if 1"<<endl;
vis[rw][curcl]=true;
flag2=findword(rw,curcl,ind+1);
vis[rw][curcl]=false;
if(flag2)return true;
}
if(prcl>=0&&bv[rw][prcl]==myword[ind]&&vis[rw][prcl]==false){
// cout<<"if 2"<<endl;
vis[rw][prcl]=true;
flag3=findword(rw,prcl,ind+1);
vis[rw][prcl]=false;
if(flag3)return true;
}
if(currw<row&&bv[currw][cl]==myword[ind]&&vis[currw][cl]==false){
// cout<<"if 3"<<endl;
vis[currw][cl]=true;
flag4=findword(currw,cl,ind+1);
vis[currw][cl]=false;
if(flag4)return true;
}
if(prrw>=0&&bv[prrw][cl]==myword[ind]&&vis[prrw][cl]==false){
// cout<<"if 4"<<endl;
vis[prrw][cl]=true;
flag5=findword(prrw,cl,ind+1);
vis[prrw][cl]=false;
if(flag5)return true;
}
return false;
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string>v=words;
row=board.size();
col=board[0].size();
bv=board;
vector<string>rv;
for(auto it:v){
myword=it;
bool flag=findword(0,0,0);
if(flag)rv.push_back(it);
}
return rv;
}
};





More Articles of Khitish Panigrahi:

Name Views Likes
Find and Replace Pattern 656 3
C++ implementation to find All combinations that add up to a given sum 583 0
Implementation of Donut.c 4906 1
Hamiltonian Cycle 2169 3
Add Lists 488 0
Unique Paths 501 3
Minimum Falling Path Sum 624 3
Word Break 585 3
Working of Internet 418 1
String Compression 1125 0
Palindromic Substrings 501 4
Formation of Process from Program 392 1
3Sum 462 3
Invert Binary Tree 739 4
0-1knapsack 610 2
Evaluate Reverse Polish Notation 1702 3
Permutations 405 4
Find Peak Element 1067 4
Maximum Subarray 436 5
Integer to Roman 2415 2
C++ Library for timing (Chrono Library) 1120 1
Programmatical termination of processes 495 1
Perfect Number 516 3
Number of Operations to Make Network Connected 1088 2
C++ implementation of Odd Even Linked List 832 0
Distance Between Bus Stops 571 3
Check if Binary Tree is BST 426 5
Partitioning the List 390 0
Function Pointer Typedef 1344 1
IOT SMART HOME 722 0
Friend Circles 1102 2
Remove duplicates from an unsorted linked list 529 0
Cycle in Undirected Graph 967 2
Multiple Word Searching Algorithm 470 8
Palindrome Partitioning 424 3
Find All Anagrams in a String 860 3
Path with Maximum Gold 701 3
Working of Home Networks 490 2
Container With Most Water 576 3
Loop Detection in LinkedList 326 0
Cheapest Flights Within K Stops 1440 2
C++ implementation of Partition Equal Subset Sum 423 0
C++ implementation to find Excel sheet Column Number 300 0
Longest Palindromic Subsequence (Print Subsequence) 987 2
Letter Tile Possibilities 638 3
Connect all siblings in a Binary Search Tree 777 2
Minimum Path Sum 642 3
C++ Hebb Learning Implementation 2011 0
Complete Employee Management System 6890 1
Combinations 394 7
C++ implementation of Longest Increasing Subsequence 406 0
Permutation of each other 287 0
Making HTTP Requests and Handling Callbacks 736 0
Valid Anagram 393 8
Multiply Strings 1678 5
C++ implementation to detect all the cycles in an undirected graph 1009 0
Longest Palindromic Subsequence (print only length) 415 2
Edit Distance 462 2
C++ implementation of Phone Book Management System 10250 0
Rotate Image 2131 1
C++ implementation of Road Transportation Management System 2658 0
Populating Next Right Pointers in Each Node 473 2
Last Stone Weight 1892 2
C++ implementation of Word Search 738 0
C++ implementation of Subsets with duplicates 325 0
Intersection of Two Linked Lists 412 3
Operator Overloading concepts in C++ 412 0
C++ implementation of Validate IP Address 2680 0
C++ implementation of Indian Railways Reservation System 1041 0
C++ implementation of college and Attendance management 3834 0
Maximum Depth of Binary Tree 526 3
Fibonacci Number 439 5
C++ implementation to Add Strings 411 0
Variadic function in C/ C++ 658 1
Boats to Save People 878 3
C++ implementation to detect cycle in a directed graph 2152 0
Pointer to Struct 571 1
House Robber with houses arranged in circular manner 871 3
Find Single Non-repeated Number 531 3
Setting up server 334 0
The k-th Lexicographical String of All Happy Strings of Length n 692 3
Unique Paths with obstacles 650 2
longest palindromic substring(improved) 408 2
Factorial Trailing Zeroes 407 2
String Rotation 916 0
C++ implementation of Bus Booking System 3602 0
3Sum Closest 505 2
kth to last element of a singly linked list 541 0
Jump Game 723 3
Maximum Product Subarray 376 4
Longest Common Subsequence (Print only Length) 608 2
ZigZag Conversion 753 4
Implement an algorithm to determine if a string has all unique characters 390 0
Relationship between IoT and cloud computing 927 1
Last Stone Weight II(any weight can be picked) 390 0
Commutable Islands 1518 2
Longest Substring Without Repeating Characters 490 4
Longest Arithmetic Sequence 803 3
Multiple Booting Guide with detail explanation of working 397 1
Minimum number of Perfect square needed to form a number 476 7
C++ implementation of Minimum number of Perfect square needed to form a number 363 0
Combination Sum 1117 4
Max Area of Island 525 3
Letter Combinations of a Phone Number 808 4
One Distance Away 432 0
Remove Nth Node From End of List 484 6
Concept of Signed and Unsigned Numbers 619 1
Time Needed to Inform All Employees 881 2
Best Time to Buy and Sell Stock 1506 3
Top K Frequent Elements 622 7
Intersection in LinkedList 569 0
Detailed analysis of Complex number using C++ 405 1
Implement strStr() 1109 4
Check Palindrome Permutation 365 0
Maximum Length of a Concatenated String with Unique Characters 555 3
Hamiltonian Path 2381 3
Relative Sort Array 418 3
Sequential Digits 593 3
Binary Tree Zigzag Level Order Traversal 385 4
C++ implementation of Shortest Path Problem 405 0
Roman to Integer 845 2
Delete a node from BST in C++ 451 3
Number of Matching Subsequences 539 3
C++ MOVIE TICKET BOOKING SYSTEM 12851 0
Number of Islands 487 3
Course Schedule II (print the order) 412 2
Permutation Sequence 515 16
Stack Pushing Game(Push Dominoes Game) 922 3
Inheritance implementation in C++ 456 0
Complete Restaurant/canteen management system 7708 0
Valid Palindrome 842 4
Course Schedule 886 2
Longest Palindromic Substring 389 2
C++ implementation of finding Kth Smallest Element in a BST 453 0
Travelling Salesman Problem 1798 3
Dijkstra 970 2
C++ implementation of Permutation with duplicates 528 0
Priority Queue 476 0
Deadlock Simulator in C++ 2759 0
Permutation Sequence 378 4
Maximal Square 486 3
C++ implementation of Is Subsequence Program 1205 0
C++ implementation of Coin Change 989 0
House Robber 628 3
4Sum 451 3
Minimum Size Subarray Sum 504 3
C++ implementation of parking management system 4877 0
Location Based Weather Predictor 1747 0
Climbing Stairs 474 5
String to Integer (atoi) 391 4
Children Sum Parent 470 5
C++ HEALTH MANAGEMENT SYSTEM 1731 0
Triangle 476 3
Majority Element 427 2
Longest Mountain in Array 780 4
Subarray Sum Equals K 541 3
Swap Nodes in Pairs 443 5
Restore IP Addresses 597 4
Convert String to URL 960 0
Create Ranges 497 3
Blood Bank Management System 3252 0
Linked List Cycle 374 6
Delete Middle Node in LinkedList 567 1
Smart and Safe Cab Finder Algorithm 1244 3
Chess Game in C++ 17498 1
Delete Node in Linked List without a head pointer 693 2
C++ Adaline Implementation 1071 0
Permutation in String 406 3
Merge Intervals 604 3
Gas Station 716 7
Increasing Triplet Subsequence 717 5
Longest Common Subsequence (Print the Subsequence) 554 2

Comments