1032-字符流

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。

例如，words = ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 'a'、'x'、'y' 和 'z'
，你所设计的算法应当可以检测到 "axyz" 的后缀 "xyz" 与 words 中的字符串 "xyz" 匹配。

按下述要求实现 StreamChecker 类：

  • StreamChecker(String[] words) ：构造函数，用字符串数组 words 初始化数据结构。
  • boolean query(char letter)：从字符流中接收一个新字符，如果字符流中的任一非空后缀能匹配 words 中的某一字符串，返回 true ；否则，返回 false。

示例：

**输入：**
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
**输出：**
[null, false, false, false, true, false, true, false, false, false, false, false, true]

**解释：**
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // 返回 False
streamChecker.query("b"); // 返回 False
streamChecker.query("c"); // 返回n False
streamChecker.query("d"); // 返回 True ，因为 'cd' 在 words 中
streamChecker.query("e"); // 返回 False
streamChecker.query("f"); // 返回 True ，因为 'f' 在 words 中
streamChecker.query("g"); // 返回 False
streamChecker.query("h"); // 返回 False
streamChecker.query("i"); // 返回 False
streamChecker.query("j"); // 返回 False
streamChecker.query("k"); // 返回 False
streamChecker.query("l"); // 返回 True ，因为 'kl' 在 words 中

提示：

  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 200
  • words[i] 由小写英文字母组成
  • letter 是一个小写英文字母
  • 最多调用查询 4 * 104 次

方法一：AC 自动机

思路

这题需要用到 AC 自动机的数据结构，概念可以参照「AC 自动机 」。

首先需要将字符串数组 words 中的单词构建一棵字典树。字典树的节点 TrieNode 有三个元素：

  1. children，长度为 26 的数组，元素均为 TrieNode；
  2. isEnd，布尔值，表示当前节点是否为一个单词的结尾；
  3. fail，失配指针，后文会继续提到。

构建字典树的步骤比较常规，将 word 一一插入字典树，并给结尾节点的 isEnd 赋为 true。这里需要记住的是，此时字典树中的每一个非空节点，都表示字符串数组 words 的某个前缀，且节点的深度就是该前缀的长度。

接下来需要更新每个非空节点的失配指针。失配指针的定义是，可以表示当前节点的最长后缀的节点，具体解释如下：当前节点能表示字符串数组 words 的某个前缀 pre}_1，我们需要找到字典树中的另一个节点，且该节点表示的前缀 pre}_2，是 pre}_1 的一个后缀，并且是能在字典树中找到的最长的后缀。那么如何更新所有节点的失配指针呢？首先，特殊地，我们将根节点和所有根节点的非空子节点的失配指针指向根节点，然后思考如何计算其他非空节点的失配指针。

当我们要计算某个节点 u 的失配指针时，假设所有比 u 浅的节点的失配指针已经计算完毕，设 u 的父节点为 p，节点 p 依靠字符 c 指向节点 u（即节点 u 代表的前缀 pre}_u 比节点 p 代表的前缀 pre}_p 多一个字符 c）。我们需要考察 p.\textit{fail 依靠字符 c 指向的节点是否非空，如果非空，我们就找到 u 的失配节点，如果为空，我们需要继续考察 p.\textit{fail}.\textit{fail，直到在这条失配链上找到一个节点，它依靠字符 c 指向的子节点非空；或者我们在失配链上不断考察的过程中，最终考察到了根节点，此时我们将 u 的失配节点指向根节点。这样一来，我们可以根据广度优先搜索的过程，计算出所有非空节点的失配节点。

如此，我们就可以用这棵字典树来匹配后缀数据流了。初始化时，设置一个指针 temp 指向根节点，每接收一个字符 c，temp 先试图依靠字符 c 移动到子节点，如果子节点为空，则在失配链上不停移动，直到找到一个节点，它依靠字符 c 指向的子节点非空，这时该子节点表示的前缀，是可以匹配到的数据流里的最长后缀。注意此时，并不能立刻返回结果，需要遍历该子节点的失配链上的所有节点，如果有节点的 isEnd 值为 true，则返回 true，否则返回 false。

注意到此时已经可以解决这道题了，但是计算每个节点的失配节点和单次 query 的时间复杂度仍然较大，最差情况下，需要遍历整条失配链路才能得到结果，因此，我们在广度优先搜索时引入以下两个优化：

  1. 当节点 p 的依靠字符 c 指向的子节点 u 为空时，将其指向 p.\textit{fail 依靠字符 c 指向的子节点 v，这种类似于路径压缩的思路，使得每个空子节点最终都会指向一个非空节点，从而省去了在失配链路上不停考察的过程。
  2. 广度优先搜索过程中，节点 u 出队列时，将 u.\textit{isEnd 更新为 u.\textit{isEnd} | u.\textit{fail}.\textit{isEnd，这样每个节点的 isEnd 参数的定义就变为：当自己或者自己的某一后缀能匹配字符串数组的某个字符串时为 true。这样一来，query 时也不需要遍历失配链路了。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class StreamChecker:

    def __init__(self, words: List[str]):
        self.root = TrieNode()
        for word in words:
            cur = self.root
            for char in word:
                idx = ord(char) - ord('a')
                if not cur.children[idx]:
                    cur.children[idx] = TrieNode()
                cur = cur.children[idx]
            cur.isEnd = True
        
        self.root.fail = self.root
        q = deque()
        for i in range(26):
            if self.root.children[i]:
                self.root.children[i].fail = self.root
                q.append(self.root.children[i])
            else:
                self.root.children[i] = self.root
        while q:
            node = q.popleft()
            node.isEnd = node.isEnd or node.fail.isEnd
            for i in range(26):
                if node.children[i]:
                    node.children[i].fail = node.fail.children[i]
                    q.append(node.children[i])
                else:
                    node.children[i] = node.fail.children[i]

        self.temp = self.root
            
    def query(self, letter: str) -> bool:
        self.temp = self.temp.children[ord(letter) - ord('a')]
        return self.temp.isEnd

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False
        self.fail = None
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class StreamChecker {
    TrieNode root;
    TrieNode temp;

    public StreamChecker(String[] words) {
        root = new TrieNode();
        for (String word : words) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if (cur.getChild(index) == null) {
                    cur.setChild(index, new TrieNode());
                }
                cur = cur.getChild(index);
            }
            cur.setIsEnd(true);
        }
        root.setFail(root);
        Queue<TrieNode> q = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if(root.getChild(i) != null) {
                root.getChild(i).setFail(root);
                q.add(root.getChild(i));
            } else {
                root.setChild(i, root);
            }
        }
        while (!q.isEmpty()) {
            TrieNode node = q.poll();
            node.setIsEnd(node.getIsEnd() || node.getFail().getIsEnd());
            for (int i = 0; i < 26; i++) {
                if(node.getChild(i) != null) {
                    node.getChild(i).setFail(node.getFail().getChild(i));
                    q.offer(node.getChild(i));
                } else {
                    node.setChild(i, node.getFail().getChild(i));
                }
            }
        }

        temp = root;
    }

    public boolean query(char letter) {
        temp = temp.getChild(letter - 'a');
        return temp.getIsEnd();
    }
}

class TrieNode {
    TrieNode[] children;
    boolean isEnd;
    TrieNode fail;

    public TrieNode() {
        children = new TrieNode[26];
    }

    public TrieNode getChild(int index) {
        return children[index];
    }

    public void setChild(int index, TrieNode node) {
        children[index] = node;
    }

    public boolean getIsEnd() {
        return isEnd;
    }

    public void setIsEnd(boolean b) {
        isEnd = b;
    }

    public TrieNode getFail() {
        return fail;
    } 

    public void setFail(TrieNode node) {
        fail = node;
    } 
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
public class StreamChecker {

    TrieNode root;
    TrieNode temp;

    public StreamChecker(String[] words) {
        root = new TrieNode();
        foreach (String word in words) {
            TrieNode cur = root;
            foreach (char ch in word) {
                int index = ch - 'a';
                if (cur.getChild(index) == null) {
                    cur.setChild(index, new TrieNode());
                }
                cur = cur.getChild(index);
            }
            cur.setIsEnd(true);
        }
        root.setFail(root);
        Queue<TrieNode> q = new Queue<TrieNode>();
        for (int i = 0; i < 26; i++) {
            if(root.getChild(i) != null) {
                root.getChild(i).setFail(root);
                q.Enqueue(root.getChild(i));
            } else {
                root.setChild(i, root);
            }
        }
        while (q.Count > 0) {
            TrieNode node = q.Dequeue();
            node.setIsEnd(node.getIsEnd() || node.getFail().getIsEnd());
            for (int i = 0; i<26; i++) {
                if(node.getChild(i) != null) {
                    node.getChild(i).setFail(node.getFail().getChild(i));
                    q.Enqueue(node.getChild(i));
                } else {
                    node.setChild(i, node.getFail().getChild(i));
                }
            }
        }

        temp = root;
    }

    public bool Query(char letter) {
        temp = temp.getChild(letter - 'a');
        return temp.getIsEnd();
    }
}

class TrieNode {
    TrieNode[] children;
    bool isEnd;
    TrieNode fail;

    public TrieNode() {
        children = new TrieNode[26];
    }

    public TrieNode getChild(int index) {
        return children[index];
    }

    public void setChild(int index, TrieNode node) {
        children[index] = node;
    }

    public bool getIsEnd() {
        return isEnd;
    }

    public void setIsEnd(bool b) {
        isEnd = b;
    }

    public TrieNode getFail() {
        return fail;
    } 

    public void setFail(TrieNode node) {
        fail = node;
    } 
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
typedef struct TrieNode {
    vector<TrieNode *> children;
    bool isEnd;
    TrieNode *fail;
    TrieNode() {
        this->children = vector<TrieNode *>(26, nullptr);
        this->isEnd = false;
        this->fail = nullptr;
    }
};

class StreamChecker {
public:
    TrieNode *root;
    TrieNode *temp;
    StreamChecker(vector<string>& words) {
        root = new TrieNode();
        for (string &word : words) {
            TrieNode *cur = root;
            for (int i = 0; i < word.size(); i++) {
                int index = word[i] - 'a';
                if (cur->children[index] == nullptr) {
                    cur->children[index] = new TrieNode();
                }
                cur = cur->children[index];
            }
            cur->isEnd = true;
        }
        root->fail = root;
        queue<TrieNode *> q;
        for (int i = 0; i < 26; i++) {
            if(root->children[i] != nullptr) {
                root->children[i]->fail = root;
                q.emplace(root->children[i]);
            } else {
                root->children[i] = root;
            }
        }
        while (!q.empty()) {
            TrieNode *node = q.front();
            q.pop();
            node->isEnd = node->isEnd || node->fail->isEnd;
            for (int i = 0; i < 26; i++) {
                if(node->children[i] != nullptr) {
                    node->children[i]->fail = node->fail->children[i];
                    q.emplace(node->children[i]);
                } else {
                    node->children[i] = node->fail->children[i];
                }
            }
        }

        temp = root;
    }
    
    bool query(char letter) {
        temp = temp->children[letter - 'a'];
        return temp->isEnd;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#define MAX_QUEUE_SIZE 81920

typedef struct TrieNode {
    struct TrieNode *children[26];
    struct TrieNode *fail;
    bool isEnd;
} TrieNode;

typedef struct {
    TrieNode *root;
    TrieNode *temp;
} StreamChecker;

TrieNode* trieNodeCreate() {
    TrieNode *obj = (TrieNode *)malloc(sizeof(TrieNode));
    for (int i = 0; i < 26; i++) {
        obj->children[i] = NULL;
    }
    obj->isEnd = false;
    obj->fail = NULL;
    return obj;
}

void freeTrieNode(TrieNode* root) {
    for (int i = 0; i < 26; i++) {
        if (root->children[i]) {
            freeTrieNode(root->children[i]);
        }
    }
    free(root);
}

StreamChecker* streamCheckerCreate(char ** words, int wordsSize) {
    StreamChecker *obj = (StreamChecker *)malloc(sizeof(StreamChecker));
    obj->root = trieNodeCreate();
    obj->temp = obj->root;
    for (int i = 0; i < wordsSize; i++) {
        TrieNode *cur = obj->root;
        for (int j = 0; words[i][j] != '\0'; j++) {
            int index = words[i][j] - 'a';
            if (cur->children[index] == NULL) {
                cur->children[index] = trieNodeCreate();
            }
            cur = cur->children[index];
        }
        cur->isEnd = true;
    }
    obj->root->fail = obj->root;
    TrieNode *queue[MAX_QUEUE_SIZE];
    int head = 0;
    int tail = 0;
    for (int i = 0; i < 26; i++) {
        if(obj->root->children[i] != NULL) {
            obj->root->children[i]->fail = obj->root;
            queue[tail++] = obj->root->children[i];
        } else {
            obj->root->children[i] = obj->root;
        }
    }
    while (head != tail) {
        TrieNode *node = queue[head++];
        node->isEnd = node->isEnd || node->fail->isEnd;
        for (int i = 0; i < 26; i++) {
            if(node->children[i] != NULL) {
                node->children[i]->fail = node->fail->children[i];
                queue[tail++] = node->children[i];
            } else {
                node->children[i] = node->fail->children[i];
            }
        }
    }
    return obj;
}

bool streamCheckerQuery(StreamChecker* obj, char letter) {
    obj->temp = obj->temp->children[letter - 'a'];
    return obj->temp->isEnd;
}

void streamCheckerFree(StreamChecker* obj) {
    free(obj);
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
var StreamChecker = function(words) {
    const root = new TrieNode();
    for (const word of words) {
        let cur = root;
        for (let i = 0; i < word.length; i++) {
            const index = word[i].charCodeAt() - 'a'.charCodeAt();
            if (cur.getChild(index) === 0) {
                cur.setChild(index, new TrieNode());
            }
            cur = cur.getChild(index);
        }
        cur.setIsEnd(true);
    }
    root.setFail(root);
    const q = [];
    for (let i = 0; i < 26; i++) {
        if(root.getChild(i) != 0) {
            root.getChild(i).setFail(root);
            q.push(root.getChild(i));
        } else {
            root.setChild(i, root);
        }
    }
    while (q.length) {
        const node = q.shift();
        node.setIsEnd(node.getIsEnd() || node.getFail().getIsEnd());
        for (let i = 0; i < 26; i++) {
            if(node.getChild(i) != 0) {
                node.getChild(i).setFail(node.getFail().getChild(i));
                q.push(node.getChild(i));
            } else {
                node.setChild(i, node.getFail().getChild(i));
            }
        }
    }

    this.temp = root;
};

StreamChecker.prototype.query = function(letter) {
    this.temp = this.temp.getChild(letter.charCodeAt() - 'a'.charCodeAt());
    return this.temp.getIsEnd();
};

class TrieNode {
    constructor() {
        this.children = new Array(26).fill(0);
        this.isEnd = false;
        this.fail;
    }

    getChild(index) {
        return this.children[index];
    }

    setChild(index, node) {
        this.children[index] = node;
    }

    getIsEnd() {
        return this.isEnd;
    }

    setIsEnd(b) {
        this.isEnd = b;
    }

    getFail() {
        return this.fail;
    }

    setFail(node) {
        this.fail = node;
    }
}

复杂度分析

  • 时间复杂度：O(L+q)，其中 L 是字符串数组总的字符数，q 是查询次数。构建字典树需要消耗 O(L) 的时间，单次查询的时间复杂度为 O(1)。

  • 空间复杂度：O(L)。构建字典树需要消耗 O(L) 的空间。

 Comments
On this page
1032-字符流