Word Search

Word Search I

Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Solution

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

Word Search II
Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

Solution

class Solution {
public:
    bool help(vector<vector<char>>& board, vector<vector<bool>>& visited, string s, int i, int j) {
        if ( s == "" ) return true;
        int m = board.size();
        int n = board[0].size();
        if ( i <= -1 or i >= m or j <= -1 or j >= n ) return false;
        if ( board[i][j] != s[0] or visited[i][j] ) return false;
        visited[i][j] = true;
        if ( help(board, visited, s.substr(1), i-1, j) ) return true;
        if ( help(board, visited, s.substr(1), i+1, j) ) return true;
        if ( help(board, visited, s.substr(1), i, j-1) ) return true;
        if ( help(board, visited, s.substr(1), i, j+1) ) return true;
        visited[i][j] = false;
        return false;
    }
    bool canFind(vector<vector<char>>& board, string s) {
        int m = board.size();
        int n = board[0].size();
        for ( int i = 0; i <= m-1; i++ ) {
            for ( int j = 0; j <= n-1; j++) {
                vector<vector<bool>> visited(m, vector<bool>(n, false));
                if ( help(board, visited, s, i, j) ) return true;
            }
        }
        return false;
    }
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> res;
        int m = board.size();
        if ( m == 0 ) return res;
        int n = board[0].size();
        if ( n == 0 ) return res;
        for ( auto s: words ) {
            if ( canFind(board, s) ) res.push_back(s);
        }
        return res;
    }
};

TrieTree Solution!!

class Solution {
public:
    struct TrieNode {
        unordered_map<char, TrieNode*> next;
        string s;
        bool isEnd, hasFound;
        TrieNode(): s(""), isEnd(false), hasFound(false) {};
    };

    TrieNode* root;

    void insert(TrieNode* root, string s) {
        TrieNode* p = root;
        int n = s.size();
        for ( int i = 0; i < n; i++ ) {
            if ( p->next.find(s[i]) == p->next.end() ) {
                p->next[s[i]] = new TrieNode();
            }
            p = p->next[s[i]];
        }
        p->isEnd = true;
        p->s = s;
        return;
    }
    void search(vector<vector<char>>& board, int i, int j, TrieNode* p, vector<vector<bool>>& available, vector<string>& res) {
        int mb = board.size(), nb = board[0].size();
        if ( i < 0 or i >= mb or j < 0 or j >= nb ) return;
        if ( not available[i][j] ) return;
        if ( p->next.find(board[i][j]) == p->next.end() ) return;
        p = p->next[board[i][j]];
        if ( p->isEnd and not p->hasFound ) res.push_back(p->s);
        p->hasFound = true;
        available[i][j] = false;
        search(board, i-1, j, p, available, res);
        search(board, i+1, j, p, available, res);
        search(board, i, j-1, p, available, res);
        search(board, i, j+1, p, available, res);
        available[i][j] = true;
        return;
    }
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> res;
        int mb = board.size();
        if ( mb == 0 ) return res;
        int nb = board[0].size();
        if ( nb == 0 ) return res;
        root = new TrieNode();
        int n = words.size();
        for ( int i = 0; i < n; i++ ) insert(root, words[i]);
        TrieNode* p;
        for ( int i = 0; i < mb; i++ ) {
            for ( int j = 0; j < nb; j++ ) {
                vector<vector<bool>> available(mb, vector<bool>(nb, true));
                search(board, i, j, root, available, res);
            }
        }
        return res;
    }
};