aboutsummaryrefslogtreecommitdiff
path: root/word_search.c
blob: dceb401339ead88b3f12d20cf2c970944ffc9116 (plain)
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
// 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;
}