Word Search

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.

For example,
Given board =

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

解题思路：

回溯法。用一个二维数组标记是否已经访问，然后朝上下左右四个方向进行扩展即可。

class Solution {
public:
    bool exist(vector>& board, string word) {
        int len = word.length();
        if(len==0){
            return true;
        }
        int m = board.size();
        if(m==0){
            return false;
        }
        int n = board[0].size();
        if(n==0){
            return false;
        }
        vector> flag(m, vector(n, false));
        for(int i=0; i>& board, vector>& flag, int i, int j, int index, string& word){
        if(index>=word.length()){
            return true;
        }
        int m = board.size();
        int n = board[0].size();
        if(i<0 || i>=m || j<0 || j>=n || flag[i][j] || board[i][j]!=word[index]){
            return false;
        }
        flag[i][j] = true;
        bool result = helper(board, flag, i+1, j, index + 1, word) ||
                      helper(board, flag, i, j+1, index + 1, word) ||
                      helper(board, flag, i-1, j, index + 1, word) ||
                      helper(board, flag, i, j-1, index + 1, word);
        flag[i][j] = false;
        return result;
    }
};

相关博文：

定制桌面成功案例

海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）

汉字转拼音c/c++源码，支持gb2312和utf8

数据库顶级会议——SIGMOD介绍