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
Rotate Image 142 0
Edit Distance 88 1
Integer to Roman 117 2
Roman to Integer 107 2
Shortest Path Problem 111 2
Dijkstra 115 2
Hamiltonian Path 105 3
Travelling Salesman Problem 109 3
Hamiltonian Cycle 108 3
Number of Operations to Make Network Connected 104 2
Time Needed to Inform All Employees 101 2
Last Stone Weight II(any weight can be picked) 113 2
Last Stone Weight 119 2
Course Schedule II (print the order) 91 2
Course Schedule 103 2
0-1knapsack 116 2
Commutable Islands 224 2
Cheapest Flights Within K Stops 114 2
Friend Circles 99 2
Longest Palindromic Subsequence (Print Subsequence) 107 2
Longest Palindromic Subsequence (print only length) 98 2
longest palindromic substring(improved) 95 2
Longest Common Subsequence (Print the Subsequence) 98 2
Longest Common Subsequence (Print only Length) 100 2
Cycle in Undirected Graph 122 2
IOT SMART HOME 142 2
Working of Home Networks 100 2
Smart and Safe Cab Finder Algorithm 147 2
Minimum Falling Path Sum 175 3
Maximum Length of a Concatenated String with Unique Characters 100 3
Stack Pushing Game(Push Dominoes Game) 101 3
Boats to Save People 120 3
Find Single Non-repeated Number 96 3
Create Ranges 90 3
Triangle 95 3
Restore IP Addresses 100 4
Number of Matching Subsequences 89 3
Max Area of Island 101 3
Number of Islands 85 3
Is Subsequence 99 3
Word Break 98 3
Perfect Number 97 3
Longest Arithmetic Sequence 95 3
Container With Most Water 101 3
Maximal Square 95 3
Best Time to Buy and Sell Stock 100 3
Distance Between Bus Stops 97 3
Validate IP Address 110 3
Longest Mountain in Array 105 4
Sequential Digits 101 3
Path with Maximum Gold 112 3
House Robber with houses arranged in circular manner 127 3
Increasing Triplet Subsequence 110 5
4Sum 106 3
3Sum 97 3
ZigZag Conversion 133 4
House Robber 97 3
Minimum Path Sum 98 3
Unique Paths with obstacles 90 2
Find and Replace Pattern 100 3
Minimum Size Subarray Sum 97 3
Maximum Subarray 103 5
Find All Anagrams in a String 65 3
Permutation in String 66 3
Subarray Sum Equals K 102 3
Maximum Product Subarray 81 4
Permutation with duplicates 77 6
Subsets with duplicates 77 7
Partition Equal Subset Sum 69 5
Relative Sort Array 65 3
Permutations 67 4
Combination Sum 125 4
All combinations that add up to a given sum 69 3
Combinations 84 7
Palindrome Partitioning 70 3
Climbing Stairs 86 5
Fibonacci Number 83 5
Unique Paths 76 3
Longest Increasing Subsequence 66 8
Gas Station 75 7
Minimum number of Perfect square needed to form a number 60 7
Permutation Sequence 142 16
Coin Change 71 6
Multiple Word Searching Algorithm 79 8
Word Search 67 6
Valid Anagram 91 8
Remove Nth Node From End of List 90 6
Linked List Cycle 67 6
Implement strStr() 67 4
Odd Even Linked List 60 6
Valid Palindrome 64 4
Maximum Depth of Binary Tree 60 3
Binary Tree Zigzag Level Order Traversal 78 4
Kth Smallest Element in a BST 47 2
Evaluate Reverse Polish Notation 64 3
String to Integer (atoi) 82 4
Intersection of Two Linked Lists 69 3
Multiply Strings 70 5
Palindromic Substrings 59 4
Add Strings 56 2
Longest Substring Without Repeating Characters 63 4
Longest Palindromic Substring 62 2
Jump Game 68 3
Majority Element 59 2
Top K Frequent Elements 91 7
Factorial Trailing Zeroes 53 2
Excel Sheet Column Number 55 3
Find Peak Element 84 4
Merge Intervals 57 3
Letter Combinations of a Phone Number 69 4
Populating Next Right Pointers in Each Node 66 2
Invert Binary Tree 62 4
Swap Nodes in Pairs 60 5
3Sum Closest 56 2
Permutation Sequence 85 4
Letter Tile Possibilities 124 3
The k-th Lexicographical String of All Happy Strings of Length n 70 3
Children Sum Parent 129 5
Check if Binary Tree is BST 126 5
Delete Node in Linked List without a head pointer 96 2
Connect all siblings in a Binary Search Tree 86 2
Delete a node from BST in C++ 96 3

Comments