date: 2020/02/02


基本概念

image.png

image.png


208实现Trie前缀树(中等)

https://leetcode-cn.com/problems/implement-trie-prefix-tree

class Trie {
private:
    bool is_string;   // 该结点位置代表一个有效字符串
    char _data;   // 结点表示的字符串
    vector<Trie*> _children;    // 子结点vec
public:
    // 构造和析构
    Trie() : _data(0), is_string(false){
        _children.assign(26, 0);
    }
    Trie(char c) : _data(c), is_string(false){
        _children.assign(26, 0);
    }
    ~Trie(){
        for(int i = 0; i < _children.size(); i++)
            delete _children[i];
    }

    // 获取下一个字符对应的子树
    Trie* get(char c){
        return _children[c - 'a'];
    }

    // 获取下一个字符对应的子树(如果不存在则创建一个空白结点)
    Trie* setDefault(char c){
        if(_children[c - 'a'] == NULL)
            _children[c - 'a'] = new Trie(c);
        return _children[c - 'a'];
    }

    // 插入新字符串,空间O(n)时间O(n)
    void insert(string word) {
        Trie* node = this;
        for(int i = 0; i < word.size(); i++)
            node = node->setDefault(word[i]);
        node->is_string = true;
    }

    // 辅助函数:判断prefix是否包含在树中,并且返回尾部结点
    Trie* startsWithReturnEnd(string& prefix){
        Trie* node = this;
        for(int i = 0; i < prefix.size(); i++){
            if(node == NULL) return NULL;
            node = node->get(prefix[i]);
        }
        return node;
    }

    // 判断prefix是否包含在树中,空间O(1)时间O(n)
    bool startsWith(string prefix) {
        return startsWithReturnEnd(prefix) != NULL;
    }

    // 判断word是否在树中(注意查找字符串要求is_string),空间O(1)时间O(n)
    bool search(string word) {
        Trie* end = startsWithReturnEnd(word);
        return end != NULL && end->is_string;
    }
};


079单词搜索(中等)

https://leetcode-cn.com/problems/word-search

DFS + 回溯,测试样例中有尺寸大于64的二维网络,不方便使用bitmap存储状态

bool helper(vector<vector<char>>& board, vector<vector<bool>>& status, string& word,
            int word_idx, int cur_row, int cur_col){
    if(word[word_idx] != board[cur_row][cur_col])
        return false;
    else if(word.size() - 1 == word_idx)
        return true;

    const int offset_row[] = {0, 1, 0, -1};
    const int offset_col[] = {1, 0, -1, 0};
    for(int i = 0; i < 4; i++){
        int row = cur_row + offset_row[i];
        int col = cur_col + offset_col[i];
        if(row < 0 || col < 0 || row >= board.size() || col >= board[0].size())
            continue;

        if(!status[row][col]){
            status[row][col] = true;
            if(helper(board, status, word, word_idx + 1, row, col))
                return true;
            status[row][col] = false;
        }
    }
    return false;
}

bool exist(vector<vector<char>>& board, string word) {
    vector<vector<bool>> status(board.size(), vector<bool>(board[0].size(), false));
    for(int i = 0; i < board.size(); i++){
        for(int j = 0; j < board[0].size(); j++){
            status[i][j] = true;
            if(helper(board, status, word, 0, i, j))
                return true;
            status[i][j] = false;
        }
    }
    return false;
}


212单词搜索II(困难)

https://leetcode-cn.com/problems/word-search-ii

079单词搜索 的进阶版,从 判断一个单词在二维网络中是否存在 升级为 给定一组单词找出其中存在于(不需要同时存在)二维网络中的所有单词