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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

#include <vector>
#include <iostream>

using namespace std;

/**
* Check if word starts wiht pos exits in board or not
* @param board
* @param i search board from row i
* @param j search board from row j
* @param word word to find
* @param pos [description]
* @return [description]
*/
bool exist(vector<vector<char> > &board, int i, int j, string &word, int pos) { if (word.size() == pos) return true; if (i < 0 || board.size() <= i || j < 0 || board[0].size() <= j) return false; const char c = word[pos]; if (c != board[i][j]) return false; board[i][j] = '\0'; // mark the board to indicate the char is used ++pos; bool exists = false; if (exist(board, i-1, j, word, pos) || exist(board, i, j-1, word, pos) || exist(board, i+1, j, word, pos) || exist(board, i, j+1, word, pos) ) exists = true; board[i][j] = c; // set back character for backtracing return exists; } bool exist(vector<vector<char> > &board, string word) { size_t sizeI = board.size(); if (sizeI <= 0) return false; size_t sizeJ = board[0].size(); for (size_t i = 0; i < sizeI; ++i) { for (size_t j = 0; j < sizeJ; ++j) { if (exist(board, i, j, word, 0)) return true; } } return false; } void stringArrayToVector(string *a, int sizeI, int sizeJ, vector<vector<char> > &vv) { vv.assign(sizeI, vector<char>(sizeJ)); int vI = vv.size(); int vJ = vv[0].size(); for (int i = 0; i < sizeI; ++i) { for (int j = 0; j < sizeJ; ++j) { vv[i][j] = a[i][j]; } } } int main(int argc, char const *argv[]) { string a[] = { "ABCE", "SFCS", "ADEE" }; vector<vector<char> > va; stringArrayToVector(a, 3, 4, va); string w = "ABCCED"; cout << w << (exist(va, w)? " exists": " not exist") << endl; w = "SEE"; cout << w << (exist(va, w)? " exists": " not exist") << endl; w = "ABCB"; cout << w << (exist(va, w)? " exists": " not exist") << endl; return 0; }
View Program Text


Test Status