[LintCode][DFS] Word Search

Problem

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example
Given board =

[
  "ABCE",
  "SFCS",
  "ADEE"
]

word = "ABCCED", -> returns true,

word = "SEE", -> returns true,

word = "ABCB", -> returns false.

Solution

Swift

class Solution {
  let step = [[0, 1], [1, 0], [0, -1], [-1, 0]]
  
  func exist(board: [[Character]], _ word: String) -> Bool {
    if word.characters.count == 0 {
      return true
    }
    var myBoard = board
    var myWord : [Character] = []
    for i in 0..<word.characters.count {
      myWord.append(word[word.startIndex.advancedBy(i)])
    }
    for i in 0..<board.count {
      for j in 0..<board[0].count {
        if myBoard[i][j] == word[word.startIndex] {
          let c = myBoard[i][j]
          myBoard[i][j] = "*"
          let res = dfs(&myBoard, x: i, y: j, word: &myWord, index: 1)
          if (res) {
            return true
          }
          myBoard[i][j] = c
        }
      }
    }
    return false
  }
  
  func dfs(inout board: [[Character]], x: Int, y: Int, inout word: [Character], index: Int) -> Bool {
    if word.count == index {
      return true
    }
    
    for i in 0..<4 {
      let newX = x + step[i][0]
      let newY = y + step[i][1]
      if (0 <= newX && newX < board.count && 0 <= newY && newY < board[0].count &&
        board[newX][newY] == word[index]) {
        let c = board[newX][newY]
        board[newX][newY] = "*"
        let res = dfs(&board, x: newX, y: newY, word: &word, index: index + 1)
        if res {
          return true
        }
        board[newX][newY] = c
      }
    }
    
    return false
  }
}

C++

class Solution {
private:
    int step[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public:
    /**
     * @param board: A list of lists of character
     * @param word: A string
     * @return: A boolean
     */
    bool exist(vector<vector<char> > &board, string word) {
        if (word.size() == 0) {
            return true;
        }
        for(int i = 0; i < board.size(); i++) {
            for(int j = 0; j < board[i].size(); j++) {
                if (board[i][j] == word[0]) {
                    char c = board[i][j];
                    board[i][j] = '*';
                    bool res = search(board, i, j, word, 1);
                    if (res) {
                        return true;
                    }
                    board[i][j] = c;
                }
            }
        }
        return false;
    }
    
    bool search(vector<vector<char>> &board, int x, int y, string &word, int index) {
        if (index == word.size()) {
            return true;
        }
        
        for(int i = 0; i < 4; i++) {
            int newX = x + step[i][0];
            int newY = y + step[i][1];
            if (0 <= newX && newX < board.size() && 0 <= newY && newY < board[0].size() && 
            word[index] == board[newX][newY]) {
                char c = board[newX][newY];
                board[newX][newY] = '*';
                bool res = search(board, newX, newY, word, index+1);
                if (res) {
                    return true;
                }
                board[newX][newY] = c;
            }
        }
        
        return false;
    }
};