跳转至

面试题 17.17. 多次搜索

题目描述

给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。

示例：

输入：
big = "mississippi"
smalls = ["is","ppi","hi","sis","i","ssippi"]
输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]

提示：

  • 0 <= len(big) <= 1000
  • 0 <= len(smalls[i]) <= 1000
  • smalls的总字符数不会超过 100000。
  • 你可以认为smalls中没有重复字符串。
  • 所有出现的字符均为英文小写字母。

解法

方法一：前缀树

 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
class Trie:
    def __init__(self):
        self.idx = -1
        self.children = [None] * 26

    def insert(self, word, i):
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.idx = i

    def search(self, word):
        res = []
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                return res
            node = node.children[idx]
            if node.idx != -1:
                res.append(node.idx)
        return res


class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        tree = Trie()
        for i, s in enumerate(smalls):
            tree.insert(s, i)
        n = len(smalls)
        ans = [[] for _ in range(n)]
        for i in range(len(big)):
            s = big[i:]
            for idx in tree.search(s):
                ans[idx].append(i)
        return ans

 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
class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        Trie tree = new Trie();
        int n = smalls.length;
        for (int i = 0; i < n; ++i) {
            tree.insert(smalls[i], i);
        }
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            res.add(new ArrayList<>());
        }
        for (int i = 0; i < big.length(); ++i) {
            String s = big.substring(i);
            List<Integer> t = tree.search(s);
            for (int idx : t) {
                res.get(idx).add(i);
            }
        }
        int[][] ans = new int[n][];
        for (int i = 0; i < n; ++i) {
            ans[i] = res.get(i).stream().mapToInt(Integer::intValue).toArray();
        }
        return ans;
    }
}

class Trie {
    private int idx;
    private Trie[] children;

    public Trie() {
        idx = -1;
        children = new Trie[26];
    }

    public void insert(String word, int i) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            c -= 'a';
            if (node.children[c] == null) {
                node.children[c] = new Trie();
            }
            node = node.children[c];
        }
        node.idx = i;
    }

    public List<Integer> search(String word) {
        Trie node = this;
        List<Integer> res = new ArrayList<>();
        for (char c : word.toCharArray()) {
            c -= 'a';
            if (node.children[c] == null) {
                return res;
            }
            node = node.children[c];
            if (node.idx != -1) {
                res.add(node.idx);
            }
        }
        return res;
    }
}

 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
class Trie {
private:
    vector<Trie*> children;
    int idx;

public:
    Trie()
        : children(26)
        , idx(-1) {}

    void insert(string word, int i) {
        Trie* node = this;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new Trie();
            node = node->children[idx];
        }
        node->idx = i;
    }

    vector<int> search(string word) {
        Trie* node = this;
        vector<int> res;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) return res;
            node = node->children[idx];
            if (node->idx != -1) res.push_back(node->idx);
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        Trie* tree = new Trie();
        int n = smalls.size();
        for (int i = 0; i < n; ++i) tree->insert(smalls[i], i);
        vector<vector<int>> ans(n);
        for (int i = 0, m = big.size(); i < m; ++i) {
            string s = big.substr(i, m - i);
            vector<int> t = tree->search(s);
            for (int& idx : t) ans[idx].push_back(i);
        }
        return ans;
    }
};

 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
type Trie struct {
    children [26]*Trie
    idx      int
}

func newTrie() *Trie {
    return &Trie{idx: -1}
}

func (this *Trie) insert(word string, idx int) {
    node := this
    for _, c := range word {
        idx := c - 'a'
        if node.children[idx] == nil {
            node.children[idx] = newTrie()
        }
        node = node.children[idx]
    }
    node.idx = idx
}

func (this *Trie) search(word string) []int {
    node := this
    var res []int
    for _, c := range word {
        idx := c - 'a'
        if node.children[idx] == nil {
            return res
        }
        node = node.children[idx]
        if node.idx != -1 {
            res = append(res, node.idx)
        }
    }
    return res
}

func multiSearch(big string, smalls []string) [][]int {
    tree := newTrie()
    for i, s := range smalls {
        tree.insert(s, i)
    }
    n := len(smalls)
    ans := make([][]int, n)
    for i := range big {
        s := big[i:]
        t := tree.search(s)
        for _, idx := range t {
            ans[idx] = append(ans[idx], i)
        }
    }
    return ans
}

 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
class TrieNode {
    var idx: Int
    var children: [TrieNode?]

    init() {
        self.idx = -1
        self.children = Array(repeating: nil, count: 26)
    }
}

class Trie {
    private let root: TrieNode

    init() {
        self.root = TrieNode()
    }

    func insert(_ word: String, _ index: Int) {
        var node = root
        for ch in word {
            let i = Int(ch.asciiValue! - Character("a").asciiValue!)
            if node.children[i] == nil {
                node.children[i] = TrieNode()
            }
            node = node.children[i]!
        }
        node.idx = index
    }

    func search(_ word: String) -> [Int] {
        var node = root
        var results = [Int]()
        for ch in word {
            let i = Int(ch.asciiValue! - Character("a").asciiValue!)
            if node.children[i] == nil {
                break
            }
            node = node.children[i]!
            if node.idx != -1 {
                results.append(node.idx)
            }
        }
        return results
    }
}

class Solution {
    func multiSearch(_ big: String, _ smalls: [String]) -> [[Int]] {
        let trie = Trie()
        for (index, small) in smalls.enumerated() {
            trie.insert(small, index)
        }

        var results = Array(repeating: [Int](), count: smalls.count)
        let bigChars = Array(big)

        for i in 0..<bigChars.count {
            let substring = String(bigChars[i...])
            let indices = trie.search(substring)
            for index in indices {
                results[index].append(i)
            }
        }

        return results
    }
}

评论