aboutsummaryrefslogtreecommitdiff
path: root/word_search.c
diff options
context:
space:
mode:
Diffstat (limited to 'word_search.c')
-rw-r--r--word_search.c34
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;
+}