complete using java are any computer language program 3. Develop an algorithm to
ID: 3747276 • Letter: C
Question
complete using java are any computer language program
3. Develop an algorithm to be able to do the word search. Write the algorithm in pseudocode. The word search starts with an nxn square of letters (n rows and n columns stored in an nxn two- dimensional array) and a given word to search. You should search vertically (up/down) and horizontally (left/right) (omit searching diagonally for simplicity) starting from the first letter in the two- dimensional array, continue until either the word is found or the end of the array is reached. You may need to use a stack to help remember which direction has been checked, which has not. The result has to be saved.Explanation / Answer
The below given algorithm is in Java.Here we go,
Algorithm:
/*
The complexity of the algorithm is O(n*n*m)
where, n = Number of items in each row of the respective matrix
m = Number of the characters in any of th word to search
*/
public class WordSearch {
/*
This is an boolean function which will return true if the words
is been found in the following input.
*/
public boolean consists(char[][] searchingWords, String words)
{
validatingData(searchingWords, words); // validating the data that has been inputted whether it is null or not
// Outer loop for checking the words upto it's limit
for (int u = 0; u < searchingWords.length; u++)
{
//Inner Loop for checking the words upto it's limit
for (int v = 0; v < searchingWords[u].length; v++)
{
//matching the words under certain criteria
if (matchingWords(searchingWords, u, v, words.charAt(0)))
{
//searching the whole words in all the respective directions
if (searchingWordsInnerPart(searchingWords, words, u, v))
{
//returning true if words found
return true;
}
}
}
}
// else return false.
return false;
}
/*
This is for checking all the possibilities of finding the words in the input and certain level
of directions in which the words can be found by using certain parameters.
*/
private static boolean searchingWordsInnerPart(char[][] searchingWords, String words, int p, int q)
{
// Searching words in the words that matched
if (words.isEmpty())
{
return true;
}
else
{
boolean startLetter = matchingWords(searchingWords, p, q, words.charAt(0));
if (startLetter) {
boolean dirLeft = searchingWordsInnerPart(searchingWords, words.substring(1), p - 1, q); // for dirLeft direction
boolean dirRight = searchingWordsInnerPart(searchingWords, words.substring(1), p + 1, q); // for dirRight direction
boolean dirBot = searchingWordsInnerPart(searchingWords, words.substring(1), p, q + 1); // for dirBot direction
boolean dirTop = searchingWordsInnerPart(searchingWords, words.substring(1), p, q - 1); // for dirTop direction
boolean dirTLeft = searchingWordsInnerPart(searchingWords, words.substring(1), p - 1, q - 1); // for dirTop dirLeft direction
boolean dirTRight = searchingWordsInnerPart(searchingWords, words.substring(1), p + 1, q - 1); // for dirTop dirRight direction
boolean botLeft = searchingWordsInnerPart(searchingWords, words.substring(1), p - 1, q + 1); // for dirBot dirLeft direction
boolean botRight = searchingWordsInnerPart(searchingWords, words.substring(1), p + 1, q + 1); // for dirBot dirRight direction
return dirLeft || dirRight || dirBot || dirTop || dirTLeft || dirTRight || botLeft || botRight;
}
return false;
}
}
// For matching the words that are been inputted and searched.
private static boolean matchingWords(char[][] searchingWords, int p, int q, char ch) {
if (p < 0 || p >= searchingWords.length || q < 0 || q >= searchingWords[p].length) {
return false;
} else {
return searchingWords[p][q] == ch;
}
}
// Validating for correct data inputted.
private void validatingData(char[][] searchingWords, String words) {
if (words == null || searchingWords == null) {
throw new IllegalArgumentException("Message here");
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.