多次搜索

2021-01-09

给定一个较长字符串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中没有重复字符串。
所有出现的字符均为英文小写字母。
通过次数4,548提交次数10,480

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/multi-search-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        Trie root = new Trie();
        for (int i = 0; i < smalls.length; i++) {
            root.insert(smalls[i]);
        }
        Map<String, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < big.length(); i++) {
            for (int j = i; j < big.length(); j++) {
                String temp = big.substring(i, j + 1);
                if (root.search(temp)) {
                    List<Integer> list = map.getOrDefault(temp, new ArrayList<>());
                    list.add(i);
                    map.put(temp, list);
                }
            }
        }

        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < smalls.length; i++) {
            List<Integer> resList = map.getOrDefault(smalls[i], new ArrayList<>());
            int[] temp = new int[resList.size()];
            for (int j = 0; j < resList.size(); j++) {
                temp[j] = resList.get(j);
            }
            list.add(temp);
        }
        return list.toArray(new int[list.size()][]);
    }

    class Trie {
        private boolean isEnd = false;
        private Trie next[] = null;

        public Trie() {
            next = new Trie[26];
        }

        public void insert(String word) {
            Trie root = this;

            char words[] = word.toCharArray();
            for (char c : words) {
                int index = c - 'a';
                if (root.next[index] == null) root.next[index] = new Trie();
                root = root.next[index];
            }
            root.isEnd = true;
        }

        public boolean search(String word) {
            Trie root = this;
            char words[] = word.toCharArray();
            for (char c : words) {
                int index = c - 'a';
                if (root.next[index] == null) return false;
                root = root.next[index];
            }
            return root.isEnd;
        }
    }
}

高效的写法1

class TrieNode{
    TrieNode[] childs;
    boolean isEnd;
    public TrieNode(){
        childs = new TrieNode[26];
    }
}
class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        TrieNode root = new TrieNode();
        Map<String,List<Integer>> map = new HashMap<>();
        //构建字典树
        for (String small : smalls) {
            map.put(small,new ArrayList<>());
            insert(root,small);
        }
        //寻找所有单词在big中的起始位置，并存放在map中
        for(int i=0;i<big.length();i++){
             search(root, i, big,map);
        }
        //输出结果
        int[][] ans = new int[smalls.length][];
        for (int i = 0; i < smalls.length; i++) {
            ans[i] = map.get(smalls[i]).stream().mapToInt(Integer::valueOf).toArray();
        }
        return ans;
    }

    //构建后缀树
    public void insert(TrieNode root,String word){
        TrieNode node = root;
        for (int i = word.length()-1; i >=0; i--) {
            int idx = word.charAt(i)-'a';
            if(node.childs[idx]==null){
                node.childs[idx] = new TrieNode();
            }
            node = node.childs[idx];
        }
        node.isEnd = true; //表示单词的结尾
    }

    //寻找以endPos结尾的所有单词的起始位置
    public void search(TrieNode root,int endPos,String sentence,Map<String,List<Integer>> map){
        TrieNode node = root;
        StringBuilder builder = new StringBuilder(); //单词作为key
        for(int i=endPos;i>=0;i--){
            int idx = sentence.charAt(i)-'a';
            if(node.childs[idx]==null){
                break;
            }
            //由于字典树存的是后缀，故要倒着插入
            builder.insert(0,sentence.charAt(i));
            node = node.childs[idx];//递归寻找
            //找到某个单词，就把起始位置添加到map中
            if(node.isEnd){
                map.get(builder.toString()).add(i);
            }
        }
    }

}

作者：qi-qi-86
链接：https://leetcode-cn.com/problems/multi-search-lcci/solution/trieshu-java-by-qi-qi-86/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

高效的写法2

class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        Trie tree = new Trie(smalls);
        for (int i = 0; i < smalls.length; i++) {
            tree.insert(smalls[i], i);
        }
        char[] chars = big.toCharArray();
        int len = chars.length;
        for (int i = 0; i < len; i++) {
            tree.update(big.substring(i, len), i);
        }

        int[][] ans = new int[smalls.length][];
        for (int i = 0; i < ans.length; i++) {
            List<Integer> list = tree.lists[i];
            ans[i] = new int[list.size()];
            for (int j = 0; j < list.size(); j++) {
                ans[i][j] = list.get(j);
            }
        }
        return ans;

    }

    class Trie {
        class Node {
            int id;
            boolean flag;
            Node[] children;

            public Node() {
                id = -1;
                flag = false;
                children = new Node[26];
            }
        }

        Node root;
        List<Integer>[] lists;

        public Trie(String[] strings) {
            root = new Node();
            int len = strings.length;
            lists = new List[len];
            for (int i = 0; i < len; i++) {
                lists[i] = new ArrayList<>();
            }
        }

        public void insert(String word, int id) {
            Node p = root;
            char[] chars = word.toCharArray();
            int len = chars.length;
            for (int i = 0; i < len; i++) {
                int c = chars[i] - 97;
                if (p.children[c] == null) {
                    p.children[c] = new Node();
                }
                p = p.children[c];
            }
            p.flag = true;
            p.id = id;
        }

        public void update(String word, int offset) {
            Node p = root;
            char[] chars = word.toCharArray();
            int len = chars.length;
            for (int i = 0; i < len; i++) {
                int c = chars[i] - 97;

                if (p.children[c] == null) {
                    return;
                }
                p = p.children[c];
                if (p.flag) {
                    lists[p.id].add(offset);
                }
            }
        }
    }
}

作者：a-12-ca1eae-cae
链接：https://leetcode-cn.com/problems/multi-search-lcci/solution/java-he-triebi-jiao-ben-de-fang-fa-66mswo-zui-ai-d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。