C++

Forum

 
A method to do lookup in dictionary with a M x N board

frek (576)
Hi all,
The exercise says:
Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.
https://www.educative.io/page/5641478634209280/5676830073815040

For the C# code provided there I wrote this C++ version which doesn't write anything! 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::vector pathRow { 0, 0, 1, 1, -1, 1, -1, -1 };
std::vector pathCol { 1, -1, -1, 1, 1, 0, 0, -1 };

bool IFValid(int rowNew, int colNew, std::vector< std::vector<bool> > visited) {
	if (rowNew >= 0 && colNew >= 0 && rowNew < 3 && colNew < 3 && !visited[rowNew][colNew])
		return true;
	return false;
}

 void FindWord(std::vector< std::vector<char> > board, std::vector< std::vector<bool> > visited
	         , int row, int col, std::string word, std::vector<std::string> englishDic)
{
	if (std::find(begin(englishDic), end(englishDic), word) != end(englishDic))
		std::cout << word << '\n';

	if (board.size() == word.size())
		return;

	for (int i = 0; i < pathRow.size(); i++)
	{
		int rowNew = row + pathRow[i];
		int colNew = col + pathCol[i];
		if (IFValid(rowNew, colNew, visited))
		{
			visited[rowNew][colNew] = true;
			FindWord(board, visited, rowNew, colNew, word + board[rowNew][colNew], englishDic);
			visited[rowNew][colNew] = false;
		}
	}
}
 

int main() {
	std::vector< std::vector<char> > board{{'G', 'I', 'Z'}, 
		                                   {'U', 'E', 'K'}, 
		                                   {'Q', 'S', 'E'}};

	std::vector< std::vector<bool> > visited {{false, false, false }, 
		                                      {false, false, false }, 
		                                      {false, false, false }}; 

	std::vector<std::string> englishDictionary{"GEEKS", "QUIZ", "FOR", "GO", "EUGE"};
	std::string word;

	for (int row = 0; row < 3; row++)
		for (int col = 0; col < 3; col++)
		{
			visited[row][col] = true;
			FindWord(board, visited, 0, 0, word + board[row][col], englishDictionary);
			visited[row][col] = false;
		}

	return 0;
}


Have two questions!

First- Why doesn't the code print anything, please?
Second - Is there a better solution for such questions in C++?
Last edited on
coder777 (8444)
First- Why doesn't the code print anything, please?
Line 19 prints only when the word is in the dictionary. So I suggest that you print it for debug reasons always. So that you see what word is provided.

By the way: You provide the vectors as copies. The changes made on line 30/32 will have no effect outside
FindWord(...). You should consider to provide the vectors as reference (&) as C# always does.

Second - Is there a better solution for such questions in C++?
It's an algorithm which is usually independent from the language.
lastchance (6980)
Your code produces no answer because board.size() is (in this instance) 3, not 9. You want the total number of characters, not the number of rows.

Change line 21 to
if (board.size() * board[0].size() == word.size())



As @coder777 mentions, to improve efficiency you should pass all the vectors on lines 9, 15 and 16 by reference, not value.

Note also that
std::vector< std::vector<char> >
can often be more conveniently dealt with as
std::vector< std::string >
and lines 43-45 could be replaced by
std::vector< std::vector<bool> > visited( 3, std::vector<bool>( 3, false ) );
(with 3 a "magic number" that needs to be tied to the size of the board in general.
Last edited on
seeplus (6591)
For the C# code provided there


Isn't the purpose of an exercise like this to develop an appropriate algorithm? IMO just translating a working solution in one language into another isn't really going to teach much. The learning comes from (trying to) develop the algorithm.

NB. When code doesn't execute as expected, then the first avenue is to use the debugger to trace through the code to see where results/execution differ from that expected. Eg the debugger should have shown that changes made to visited within FindWord() weren't being reflected back to the caller. This then should have started a thought pattern that led to the reasoning that visited is being passed by value when it should be passed by ref.
Last edited on
lastchance (6980)
Passing the vectors by reference rather than value improves efficiency (by avoiding a lot of copying). That is NOT, however, why the code fails to find a solution. The algorithm doesn't need to feed back information from further down the line.

The only thing that needs to be changed to make it run is to compare word length with 9 on line 21, rather than the 3 that it currently is (i.e. board.size()). A debugger wouldn't tell you this: however, @coder77's suggestion of printing out word certainly would (and did in my case, since no word longer than 3 letters was being printed out).

Last edited on
Topic archived. No new replies allowed.