79. 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.

S：DFS

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (word.size() == 0) {
            return false;
        }
        m = board.size();
        if (m < 1) {
            return false;
        }
        n = board[0].size();
        visited = vector<vector<bool>>(m, vector<bool>(n, false));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (search(board, word, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }
    bool search(vector<vector<char> > &board, string word, int i, int j) {
        if (word[0] != board[i][j]) {
            return false;
        } else if (word.size() == 1) {
            return true;
        }
        visited[i][j] = true;
        vector<int> dx{1, 0, -1, 0};
        vector<int> dy{0, 1, 0, -1};
        string newWord = word.substr(1);
        for (int k = 0; k < 4; ++k) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (valid(x, y) && search(board, newWord, x, y)) {
                return true;
            }
        }
        visited[i][j] = false;
        return false;
    } 

    bool valid(int x, int y) {
        return x < m && x >= 0 && y < n && y >= 0 && !visited[x][y];
    }

private:
    vector<vector<bool>> visited;
    int m;
    int n;        

};

212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must 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 in a word.

S: Trie

用字典构建Tire. 如果只有26个字母可以用数组代替TireNode中的哈希表

struct TrieNode {
    char letter;
    bool isEnd;
    unordered_map<char, TrieNode* > children;
    TrieNode() {}
    TrieNode(char a): letter(a), isEnd(false) {}
};
class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        set<string> result;
        vector<string> output;
        m = board.size();
        if (m == 0) {
            return output;
        }
        n = board[0].size();
        visited = vector<vector<bool>> (m, vector<bool>(n, false));
        TrieNode root('@');
        for (string word: words) {
            constructTrie(word, &root);
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                string cur = "";
                findWord(board, i, j, cur, result, &root);
            }
        }
        for (string i: result) {
            output.push_back(i);
        }
        return output;       
    }
    void constructTrie(string word, TrieNode* root) {
        if (word.size() == 0) {
            return;
        }
        TrieNode* node;
        if (root->children.find(word[0]) == root->children.end()) {
            node = new TrieNode(word[0]);
            root->children[word[0]] = node;
        } else {
            node = root->children[word[0]];
        }
        if (word.size() == 1) {
            node->isEnd = true;
            return;
        }
        constructTrie(word.substr(1), node);
    }

    void findWord(vector<vector<char> > &board, int i, int j, string cur, set<string>& result, TrieNode* root) {
        if (root->isEnd) {
            result.insert(cur);
        }             
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || root->children.find(board[i][j]) == root->children.end()) {
            return;
        }
        vector<int> dx{0, 1, 0, -1};
        vector<int> dy{1, 0, -1, 0};
        cur += board[i][j];
        visited[i][j] = true;
        for (int k = 0; k < 4; ++k) {
            int x = i + dx[k];
            int y = j + dy[k];
            findWord(board, x, y, cur, result, root->children[board[i][j]]);
        }
        visited[i][j] = false;
    }

private:
    int m;
    int n;
    vector<vector<bool>> visited;
};

Add and Search Word

Design a data structure that supports the following two operations:addWord(word)andsearch(word)

search(word)can search a literal word or a regular expression string containing only lettersa-zor..

A.means it can represent any one letter.

Example

addWord("bad")
addWord("dad")
addWord("mad")
search("pad")  // return false
search("bad")  // return true
search(".ad")  // return true
search("b..")  // return true

S: Trie

struct TrieNode {
    bool isEnd;
    vector<TrieNode*> children;
    TrieNode(): isEnd(false), children(vector<TrieNode*>(26, NULL)) {}
};

class WordDictionary {
public:

    // Adds a word into the data structure.
    WordDictionary() {
        root = new TrieNode;
    }

    void addWord(string word) {
        hit = false;
        TrieNode* cur = root;
        for (int i = 0; i < word.size(); ++i) {
            int idx = word[i] - 'a';
            if (cur->children[idx] == NULL) {
                TrieNode* node = new TrieNode;
                cur->children[idx] = node;
            }
            cur = cur->children[idx];
        }
        cur->isEnd = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return dfsSearch(word, root);
    }

    bool dfsSearch(string word, TrieNode* root) {
        if (root == NULL) {
            return false;
        }
        if (word.size() == 0) {
            return root->isEnd;
        }
        if (word[0] == '.') {
            word = word.substr(1);
            for(const auto& child : root->children) {
                if (dfsSearch(word, child)) {
                    return true;
                }
            }
        } else {
            int idx = word[0] - 'a';
            word = word.substr(1);
            return dfsSearch(word, root->children[idx]);
        }
        return false;
    }

private:
    TrieNode *root;
};