diff options
Diffstat (limited to 'word_search.c')
-rw-r--r-- | word_search.c | 34 |
1 files changed, 34 insertions, 0 deletions
diff --git a/word_search.c b/word_search.c new file mode 100644 index 0000000..dceb401 --- /dev/null +++ b/word_search.c @@ -0,0 +1,34 @@ +// 79. Word Search +#include "leetcode.h" + +/* + * given an 'm * n' grid of characters 'board' and a string 'word', return 1 if + * the word exists in the grid. the word can be constructed from letters of + * sequentially adjacent cells, where adjacent cells are horizontally or + * vertically neighbouring the same letter cell may not be used more than once. + */ + +bool dfs(char **board, int r_size, int c_size, int r, int c, char *word, + int s_len, int k) { + if (k == s_len) + return 1; + if (r < 0 || c < 0 || r > r_size - 1 || c > c_size - 1 || + board[r][c] != word[k]) + return 0; + char tmp = board[r][c]; + bool res = dfs(board, r_size, c_size, r + 1, c, word, s_len, k + 1) | + dfs(board, r_size, c_size, r - 1, c, word, s_len, k + 1) | + dfs(board, r_size, c_size, r, c + 1, word, s_len, k + 1) | + dfs(board, r_size, c_size, r, c - 1, word, s_len, k + 1); + board[r][c] = tmp; + return res; +} + +bool exist(char **board, int boardSize, int *boardColSize, char *word) { + int r_size = boardSize, c_size = boardColSize[0], s_len = strlen(word); + for (int r = 0; r < r_size; r++) + for (int c = 0; c < c_size; c++) + if (dfs(board, r_size, c_size, r, c, word, s_len, 0)) + return 1; + return 0; +} |