LeetCode 面試題 17.17. 多次搜索

給定一個(gè)較長(zhǎng)字符串 big 和一個(gè)包含較短字符串的數(shù)組 smalls ，設(shè)計(jì)一個(gè)方法沪猴，根據(jù) smalls 中的每一個(gè)較短字符串屈扎，對(duì) big 進(jìn)行搜索信不。輸出 smalls 中的字符串在 big 里出現(xiàn)的所有位置 positions 岩四，其中 positions[i] 為 smalls[i] 出現(xiàn)的所有位置呀袱。

示例：

輸入：
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的總字符數(shù)不會(huì)超過 100000差导。
• 你可以認(rèn)為smalls中沒有重復(fù)字符串砌函。
• 所有出現(xiàn)的字符均為英文小寫字母。

前綴樹

• 用 smalls 構(gòu)造前綴樹端姚。
• 在前綴樹中查找所有 big 中由 i 到末尾的子串晕粪，若能遍歷到前綴樹中 end 不為空的節(jié)點(diǎn)，則說明該條路徑對(duì)應(yīng)的字符串（即 end 中存儲(chǔ)的字符串）在 big 中存在渐裸。

class Solution {
    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;
    }

    class Trie {
        private TreeNode root;

        public Trie(String[] words) {
            root = new TreeNode('/');
            for (String word : words) {
                insert(word);
            }
        }
        
        public void insert(String word) {
            TreeNode p = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                int index = c - 'a';
                if (p.children[index] == null) {
                    TreeNode node = new TreeNode(c);
                    p.children[index] = node;
                }
                p = p.children[index];
            }
            p.end = word;
        }
        
        public List<String> search(String word) {
            TreeNode p = root;
            List<String> res = new ArrayList<>();
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                int index = c - 'a';
                if (p.children[index] == null) {
                    break;
                }
                p = p.children[index];
                if (p.end != null) {
                    res.add(p.end);
                }
            }
            return res;
        }

        public class TreeNode {
            public char data;
            public TreeNode[] children = new TreeNode[26];
            public String end;
            public TreeNode(char data) {
                this.data = data;
            }
        }
    }
}