Tries 字典树

473. Add and Search Word - Data structure design

class TrieNode {
public:
    TrieNode * next[26];
    bool isWord;
    TrieNode() {
        for (int i = 0; i < 26; i++) {
            next[i] = NULL;
        }
        isWord = false;
    }
};
class WordDictionary {
private:
    TrieNode * root;
public:
    /*
    * @param word: Adds a word into the data structure.
    * @return: nothing
    */
    WordDictionary() {
        root = new TrieNode;
    }
    void addWord(string &word) {
        // write your code here
        TrieNode * temp = root;
        for (int i = 0; i < word.size(); i++) {
            if (temp->next[word[i] - 'a'] == NULL) {
                temp->next[word[i] - 'a'] = new TrieNode();
            }
            temp = temp->next[word[i] - 'a'];
        }
        temp -> isWord = true;
    }
    /*
    * @param word: A word could contain the dot character '.' to represent any one letter.
    * @return: if the word is in the data structure.
    */
    bool search(string &word) {
        return search(word, word.size(), 0, root);
    }
    bool search(string &word, int n, int pos, TrieNode * cur) {
        // write your code here
        if (cur == NULL) {
            return false;
        }
        if (pos == n) {
            return cur -> isWord;
        }
        if (word[pos] == '.') {
            for (int j = 0; j < 26; j++) {
                if (search(word, n, pos + 1, cur->next[j]) == true) {
                    return true;
                }
            }
            return false;
        }
        else {
            //if (cur -> next[word[pos] - 'a'])
            return search(word, n, pos + 1, cur->next[word[pos] - 'a']);
        }
    }
};

132. Word Search II

class TrieNode {
public:
    TrieNode * next[26];
    bool isWord;
    TrieNode() {
        for (int i = 0; i < 26; i++) {
            next[i] = NULL;
        }
        isWord = false;
    }
};
class Solution {
private:
    TrieNode * root;
    vector <string> res;
    vector <int> row = { -1, 0, 1, 0 };
    vector <int> column = { 0, 1, 0, -1 };
public:
    /**
    * @param board: A list of lists of character
    * @param words: A list of string
    * @return: A list of string
    */
    Solution(){
        root = new TrieNode();
    }
    vector<string> wordSearchII(vector<vector<char>> &board, vector<string> &words) {
        // write your code here
        for (int i = 0; i < words.size(); i++) {
            TrieNode * temp;
            temp = root;
            for (int j = 0; j < words[i].size(); j++) {
                if (temp->next[words[i][j] - 'a'] == NULL) {
                    temp->next[words[i][j] - 'a'] = new TrieNode();
                }
                temp = temp->next[words[i][j] - 'a'];
            }
            temp->isWord = true;
        }
        cout << 'a';
        string toNow;
        vector <vector<int>> visited(board.size(), vector<int>(board[0].size()));
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (root->next[board[i][j] - 'a'] != NULL){
                    toNow.push_back(board[i][j]);
                    visited[i][j] = 1;
                    helper(board, words, i, j, root->next[board[i][j] - 'a'], toNow, visited);
                    visited[i][j] = 0;
                    toNow.pop_back();
                }
            }
        }
        return res;

    }
    bool exist(vector<vector<char>> &board, int i, int j, vector<vector<int>> &visited) {

        if (i < 0 || i >= board.size()) {
            return false;
        }
        if (j < 0 || j >= board[0].size()) {
            return false;
        }
        if (visited[i][j] == 1)
            return false;
        return true;
    }
    void helper(vector<vector<char>> &board, vector<string> &words, int rowNow, int colNow, TrieNode * temp, string & toNow, vector<vector<int>> &visited) {
        if (temp->isWord == true) {
            vector <string> :: iterator it = find(res.begin(), res.end(), toNow);
            if (it == res.end())
                res.push_back(toNow);
        }
        for (int i = 0; i < 4; i++) {
            int nextRow = rowNow + row[i];
            int nextCol = colNow + column[i];
            if (exist(board, nextRow, nextCol, visited) && temp->next[board[nextRow][nextCol] - 'a'] != NULL) {
                toNow.push_back(board[nextRow][nextCol]);
                visited[nextRow][nextCol] = 1;
                helper(board, words, nextRow, nextCol, temp->next[board[nextRow][nextCol] - 'a'], toNow, visited);
                visited[nextRow][nextCol] = 0;
                toNow.pop_back();
            }
        }
        return;

    }
};