返回

[Leetcode]211. Add and Search Word - Data structure design

题目描述

Design a data structure that supports the following two operations:

void addWord(word) bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

例子

addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b..") -> true

Note

You may assume that all words are consist of lowercase letters a-z.

解题思路

这道题很显然是用 Trie 来做,Trie 基本概念参见 维基百科-Trie

这道题由于存在通配符 . 所以需要考虑额外的情况。我首先想到的是利用一个队列维护当前层的节点和下一层的节点,遇到 . 的时候将当前节点的下一层全部推入下一层要搜索的节点,相当于一种层序遍历的思路,代码如下:

class WordDictionary {
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        head = std::make_shared<TreeNode>();
    }

    /** Adds a word into the data structure. */
    void addWord(string word) {
        std::shared_ptr<TreeNode> current_node = head;
        for (char c: word) {
            int index = c - 'a';
            if (current_node->next_levels[index] == nullptr) {
                current_node->next_levels[index] = std::make_shared<TreeNode>();
            }
            current_node = current_node->next_levels[index];
        }
        current_node->is_word = 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) {
        std::vector<std::shared_ptr<TreeNode>> current_nodes{head};
        for (char c: word) {
            std::vector<std::shared_ptr<TreeNode>> next_nodes;
            int index = c - 'a';
            for (const auto& current_node: current_nodes) {
                if (c == '.') {
                    for (const auto next_node: current_node->next_levels) {
                        if (next_node) {
                            next_nodes.push_back(next_node);
                        }
                    }
                }
                else if (current_node->next_levels[index]) {
                    next_nodes.push_back(current_node->next_levels[index]);
                }
            }
            current_nodes = next_nodes;
            if (current_nodes.empty()) break;
        }

        for (const auto& current_node: current_nodes) {
            if (current_node->is_word) return true;
        }

        return false;

    }

private:
    struct TreeNode {
        bool is_word;
        std::vector<std::shared_ptr<TreeNode>> next_levels;

        TreeNode() {
            is_word = false;
            next_levels = std::vector<std::shared_ptr<TreeNode>>(26, nullptr);
        }

    };

    std::shared_ptr<TreeNode> head;

};

这种方法在 leetcode 上超时了,想了一下原因大概是因为层序遍历的原因,虽然避免了递归产生的空间消耗,但是不能优先搜索某一条路径,应该用前序遍历的思路来做,修改代码如下:

class WordDictionary {
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        head = std::make_shared<TreeNode>();
    }

    /** Adds a word into the data structure. */
    void addWord(string word) {
        std::shared_ptr<TreeNode> current_node = head;
        for (char c: word) {
            int index = c - 'a';
            if (current_node->next_levels[index] == nullptr) {
                current_node->next_levels[index] = std::make_shared<TreeNode>();
            }
            current_node = current_node->next_levels[index];
        }
        current_node->is_word = 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 searchAletter(head, word, 0);

    }

private:
    struct TreeNode {
        bool is_word;
        std::vector<std::shared_ptr<TreeNode>> next_levels;

        TreeNode() {
            is_word = false;
            next_levels = std::vector<std::shared_ptr<TreeNode>>(26, nullptr);
        }

    };

    bool searchAletter(const std::shared_ptr<TreeNode> node, const string& word, int index) {
        if (node == nullptr) return false;

        if (index == word.length()) return node->is_word;

        char character = word[index];
        if (character == '.') {
            for (int i = 0; i < 26; i++) {
                if (searchAletter(node->next_levels[i], word, index + 1)) return true;
            }

            return false;
        }

        return searchAletter(node->next_levels[character - 'a'], word, index + 1);
    }

    std::shared_ptr<TreeNode> head;

};
  • 时间复杂度: n 为 字符串长度
    • 添加:O(n)
    • 搜索:
      • 没有 .:O(n)
      • .:O(树节点个数)
Licensed under CC BY-NC-SA 4.0
Built with Hugo
Theme Stack designed by Jimmy