返回

[Leetcode]1032. Stream of Characters (C++)

题目描述

题目链接:1032. Stream of Characters

Implement the StreamChecker class as follows:

  • StreamChecker(words): Constructor, init the data structure with the given words.
  • query(letter): returns true if and only if for some k >= 1, the last k characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.

例子

StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // init the dictionary. streamChecker.query('a'); // return false streamChecker.query('b'); // return false streamChecker.query('c'); // return false streamChecker.query('d'); // return true, because 'cd' is in the wordlist streamChecker.query('e'); // return false streamChecker.query('f'); // return true, because 'f' is in the wordlist streamChecker.query('g'); // return false streamChecker.query('h'); // return false streamChecker.query('i'); // return false streamChecker.query('j'); // return false streamChecker.query('k'); // return false streamChecker.query('l'); // return true, because 'kl' is in the wordlist

Note

  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 2000
  • Words will only consist of lowercase English letters.
  • Queries will only consist of lowercase English letters.
  • The number of queries is at most 40000.

解题思路

这道题可以考虑成一道查找单词的题,一般查找单词的题可以考虑用字典树(前缀树)来实现。包括以下两种思路。

方法一

首先我想到的是正向的字典树,即每个单词从头到尾插入树中。查找的时候维护一个候选单词队列,候选队列中永远包含树的头。查找时对每一个候选节点进行查找下一个字母所在位置,如果可以进行到下一层则放入新的候选队列中,另外如果遇到单词则返回 true,结果会超时,因为要同时维护的过多节点,代码如下所示。

class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        m_head = new TrieNode();
        for (const std::string& word: words) {
            insertWord(word);
        }
        m_candidates.push(m_head);
    }

    bool query(char letter) {
        int index = letter - 'a';
        bool found_word = false;
        int count = m_candidates.size();
        m_candidates.push(m_head);
        while (count > 0) {
            TrieNode* candidate = m_candidates.front();
            m_candidates.pop();
            count--;
            if (!candidate->next_level[index]) continue;
            candidate = candidate->next_level[index];
            if (candidate->is_word) found_word = true;
            m_candidates.push(candidate);
        }
        return found_word;
    }

private:
    struct TrieNode {
        std::vector<TrieNode*> next_level;
        bool is_word;
        TrieNode(): next_level(26), is_word(false) {}
    };

    TrieNode* m_head;
    std::queue<TrieNode*> m_candidates;

    void insertWord(const std::string& word) {
        TrieNode* current = m_head;
        for (int i = 0; i < word.length(); i++) {
            int index = word[i] - 'a';
            if (!current->next_level[index]) {
                current->next_level[index] = new TrieNode();
            }
            current = current->next_level[index];
        }
        current->is_word = true;
    }

};
  • 时间复杂度:Solution: O(n), Query: O(N) 最坏情况是所有节点都在候选队列中(类似于 aaaaa... 的情况)
  • 空间复杂度:O(N)

方法二

方法一的弊端在于候选节点太多,如果我们反向存单词的话(从尾到头存入)。然后对于所有查询字符都存在一个字符串里,这样就变成了常规的字典树查询操作,另外由于字典树中最长存在的单词长度为 k, 所以我们存的字符串超过 k 时还可以进行裁剪,进一步优化所需空间,代码如下:

class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        m_head = new TrieNode();
        for (const std::string& word: words) {
            insertWord(word);
        }
        current_string = "";
    }

    bool query(char letter) {
        current_string += letter;
        TrieNode* curr = m_head;
        for (int i = current_string.length() - 1; i >= 0; i--) {
            if (!curr->next_level[current_string[i] - 'a']) return false;
            curr = curr->next_level[current_string[i] - 'a'];
            if (curr->is_word) return true;
        }
        return false;
    }

private:
    struct TrieNode {
        std::vector<TrieNode*> next_level;
        bool is_word;
        TrieNode(): next_level(26), is_word(false) {}
    };

    TrieNode* m_head;
    std::string current_string;

    void insertWord(const std::string& word) {
        TrieNode* current = m_head;
        for (int i = word.length() - 1; i >= 0; i--) {
            int index = word[i] - 'a';
            if (!current->next_level[index]) {
                current->next_level[index] = new TrieNode();
            }
            current = current->next_level[index];
        }
        current->is_word = true;
    }

};
  • 时间复杂度:Solution: O(n), Query: O(k) k 为单词最大长度
  • 空间复杂度:O(N)
Licensed under CC BY-NC-SA 4.0
Built with Hugo
Theme Stack designed by Jimmy