15.3.字符串操作

发表于 更新于 分类于 ， 阅读次数： 本文字数： 424 阅读时长 ≈ 2 分钟

\(15.3\)字符串操作

1.键的收集与前缀匹配

  由于在\(trie\)中，字符和键(\(key\))都是被隐性表示的，当我们想让我们的键变得可迭代时，我们不能只在\(trie\)中直接寻找它们。我们可以用一个可迭代的collect方法，该方法会维护一个字符串，它用于储存路径上的字符： 

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
public V get(String key) {
    Node x = get(root, key, 0);
    if (x == null) return null;
    return x.value;
}

private Node get(Node x, String key, int d) {
    if (x == null) return null;
    if (d == key.length()) return x;
    char c = key.charAt(d);// use dth key char of key to find subtrie
    return get(x.next[c], key, d + 1);
}

public Iterable<String> keys() { 
    return keysWithPrefix(""); 
}

//collect keys in a trie.
//the "get" method will return the node containing the prefix
//so we can collect any string that starts from this node
public Iterable<String> keysWithPrefix(String pre) {
    Queue<String> q = new Queue<String>();
    collect(get(root, pre, 0), pre, q);
    return q;
}

private void collect(Node x, String pre, Queue<String> q) {
    if (x == null) return;
    if (x.value != null) q.enqueue(pre);
    for (char c = 0; c < R; c += 1) {
        collect(x.next[c], pre + c, q);
    }
}

  整个搜索键的过程如下：

  keysWithPrefix方法的执行过程如下：

2.通配符匹配

  为了实现keysThatMatch()方法，我们使用一个类似的程序，但添加一个参数\(pat\)来表示我们需要\(collect()\)的字符串。当模式字符是通配符(\(wildcard\))时，我们调用它的所有链接；否则，我们只调用和通配符相关的链接。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public Iterable<String> keysThatMatch(String pat) {
    Queue<String> q = new Queue<String>();
    collect(root, "", pat, q);
    return q;
}

public void collect(Node x, String pre, String pat, Queue<String> q) {
    int d = pre.length();
    if (x == null) return;
    if (d == pat.length() && x.val != null) q.enqueue(pre);
    if (d == pat.length()) return;

    char next = pat.charAt(d);
    for (char c = 0; c < R; c += 1) {
        if (next == '.' || next == c) {
            collect(x.next[c]. pre + c, pat, q);
        }
    }
}