【Day 75 】2023-08-23 - 面试题 17.17 多次搜索

[azl397985856]

面试题 17.17 多次搜索

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/multi-search-lcci

前置知识

• 字符串匹配
• Trie

  题目描述

  
  给定一个较长字符串 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 中没有重复字符串。 所有出现的字符均为英文小写字母。

[freesan44]

class Solution {

    private var root = Node()

    func multiSearch(_ big: String, _ smalls: [String]) -> [[Int]] {

        let n = smalls.count
        // 初始化结果集
        var res = [[Int]](repeating: [], count: n)
        // 建树
        for i in 0..<smalls.count {
            insert(smalls[i], i)
        }

        for i in 0..<big.count {
            var tmp = root
            var j = i
            while j < big.count {
                let char = big[big.index(big.startIndex, offsetBy: j)]
                // 不存在以该串为prefix的敏感词
                if tmp.children[char] == nil {
                    break
                }

                tmp = tmp.children[char]!

                if tmp.isWord {
                    res[tmp.id].append(i)
                }

                j += 1
            }
        }
        // 返回二维数组
        var ret = [[Int]]()

        for i in 0..<n {
            ret.append(res[i])
        }

        return ret
    }

    private func insert(_ word: String, _ id: Int) {

        var tmp = root

        for char in word {
            if tmp.children[char] == nil {
                tmp.children[char] = Node()
            }

            tmp = tmp.children[char]!
        }

        tmp.isWord = true
        tmp.id = id
    }

    class Node {

        var children: [Character: Node]
        var isWord: Bool
        var id: Int

        init() {
            children = [:]
            isWord = false
            id = 0
        }
    }
}

[GuitarYs]

class SearchPositions:
    def search_positions(self, big, smalls):
        positions = []
        for small in smalls:
            indexes = []
            start_index = 0
            while True:
                index = big.find(small, start_index)
                if index == -1:
                    break
                indexes.append(index)
                start_index = index + 1
            positions.append(indexes)
        return positions

[Diana21170648]

思路

tire 暴力 KMP

代码

class Solution:
    class TrieNode:
        def __init__(self):
            self.children = [None] * 26  # 存储子节点
            self.isWord = False  # 标记是否为单词的结束
            self.id = 0  # 存储小字符串的索引

    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        root = self.TrieNode()  # 初始化根节点

        n = len(smalls)
        res = [[] for _ in range(n)]  # 初始化结果集

        # 建树
        for i in range(n):
            self.insert(root, smalls[i], i)  # 插入小字符串到 Trie 树中

        for i in range(len(big)):
            tmp = root
            for j in range(i, len(big)):
                if not tmp.children[ord(big[j]) - ord('a')]:
                    break  # 如果当前字符不存在于 Trie 树中，退出循环

                tmp = tmp.children[ord(big[j]) - ord('a')]

                if tmp.isWord:
                    res[tmp.id].append(i)  # 将找到的索引添加到结果集

        # 返回二维数组
        ret = []
        for i in range(n):
            ret.append(res[i])

        return ret

    def insert(self, root: TrieNode, word: str, id: int):
        tmp = root
        for i in range(len(word)):
            if not tmp.children[ord(word[i]) - ord('a')]:
                tmp.children[ord(word[i]) - ord('a')] = self.TrieNode()  # 创建新的节点

            tmp = tmp.children[ord(word[i]) - ord('a')]

        tmp.isWord = True  # 标记为一个单词的结束
        tmp.id = id  # 存储小字符串的索引

复杂度分析

• 时间复杂度：O(N*k)，其中 N 为敏感词最长单词长度，K为big长度。
• 空间复杂度：O(s),匹配成功位置的个数

[Beanza]

class Solution {

private var root = Node()

func multiSearch(_ big: String, _ smalls: [String]) -> [[Int]] {

    let n = smalls.count
    // 初始化结果集
    var res = [[Int]](repeating: [], count: n)
    // 建树
    for i in 0..<smalls.count {
        insert(smalls[i], i)
    }

    for i in 0..<big.count {
        var tmp = root
        var j = i
        while j < big.count {
            let char = big[big.index(big.startIndex, offsetBy: j)]
            // 不存在以该串为prefix的敏感词
            if tmp.children[char] == nil {
                break
            }

            tmp = tmp.children[char]!

            if tmp.isWord {
                res[tmp.id].append(i)
            }

            j += 1
        }
    }
    // 返回二维数组
    var ret = [[Int]]()

    for i in 0..<n {
        ret.append(res[i])
    }

    return ret
}

private func insert(_ word: String, _ id: Int) {

    var tmp = root

    for char in word {
        if tmp.children[char] == nil {
            tmp.children[char] = Node()
        }

        tmp = tmp.children[char]!
    }

    tmp.isWord = true
    tmp.id = id
}

class Node {

    var children: [Character: Node]
    var isWord: Bool
    var id: Int

    init() {
        children = [:]
        isWord = false
        id = 0
    }
}

}

[Fuku-L]

代码

class Solution {

    class Trie{
        TrieNode root;
        public Trie(String[] words){
            root = new TrieNode();
            for(String word : words){
                TrieNode node = root;
                for(char w : word.toCharArray()){
                    int i = w - 'a';
                    if(node.next[i] == null){
                        node.next[i] = new TrieNode();
                    }
                    node = node.next[i];
                }
                node.end = word;
            }
        }

        public List<String> search(String str){
            TrieNode node = root;
            List<String> res = new ArrayList<>();
            for(char c : str.toCharArray()){
                int i = c - 'a';
                if(node.next[i] == null){
                    break;
                }
                node = node.next[i];
                if(node.end != null){
                    res.add(node.end);
                }
            }
            return res;
        }  
    }

    class TrieNode{
        String end;
        TrieNode[] next = new TrieNode[26];
    }

    public int[][] multiSearch(String big, String[] smalls) {
        Trie trie = new Trie(smalls);
        Map<String, List<Integer>> hit = new HashMap<>();
        for(int i = 0; i < big.length(); i++){
            List<String> matchs = trie.search(big.substring(i));
            for(String word: matchs){
                if(!hit.containsKey(word)){
                    hit.put(word, new ArrayList<>());
                }
                hit.get(word).add(i);
            }
        }

        int[][] res = new int[smalls.length][];
        for(int i = 0; i < smalls.length; i++){
            List<Integer> list = hit.get(smalls[i]);
            if(list == null){
                res[i] = new int[0];
                continue;
            }
            int size = list.size();
            res[i] = new int[size];
            for(int j = 0; j < size; j++){
                res[i][j] = list.get(j);
            }
        }
        return res;
    }
}

[Alexno1no2]

# 思路
# trie中记录smalls中的字符串，末尾记录字符串，方便后面遍历。
# trie中的search用于搜索字符串，将搜索到的字符串存入返回值中。
# 遍历big长字符串，将其与trie匹配。
# 按smalls顺序输出最终结果

class Trie:
    def __init__(self, words):
        self.d = {}
        for word in words:
            t = self.d
            for w in word:
                if w not in t:
                    t[w] = {}
                t = t[w]
            t['end'] = word

    def search(self, s):
        t = self.d
        res = []
        for w in s:
            if w not in t:
                break
            t = t[w]
            if 'end' in t:
                res.append(t['end'])
        return res

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        trie = Trie(smalls)
        hit = collections.defaultdict(list)

        for i in range(len(big)):
            matchs = trie.search(big[i:])
            for word in matchs:
                hit[word].append(i)

        res = []
        for word in smalls:
            res.append(hit[word])
        return res