[LeetCode面试题17.17 - 多次搜索] | 刷题打卡_maybelence的专栏文章_微信文章

掘金团队号上线，助你 Offer 临门！点击查看详情

前言

今天难得偷闲，于是我在intelij上面装了一个leetcode插件，每天日常刷一刷leetcode题。就在刚刚，我刷到了这样一题。

题目描述

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

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

解题思路

看到判断字符串在母串的位置，很容易让人想到 indexOf(str) ，我们可以记录 indexOf(str) 返回值，但 smalls 中特定位的字符在big出现的次数是未知数 x ，所以可以用一个可变数组List来存储这个字符在 big 中出现的次数。而 indexOf(str) 默认返回的是 str 在母串中第一次的索引值， String 还提供了 indexOf(str,index) 来记录从第一个开始的索引值，因此可以采用 indexOf(str,index+1) 来避免记录重复值。所以解法就很简单，先用 indexOf 获取索引值，然后存储在一个长度可变的数组 List 中，接着讲 List 再转成固定长度数组，返回给 result[i] 。

class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        int [][] result = new int [smalls.length][];
        for (int i = 0; i < smalls.length ; i++) {
            if("".equals(big)){
                result[i] = new int[0];
                continue;
            }
            else if(!smalls[i].equals("")){
                int index = big.indexOf(smalls[i]);
                List<Integer> list = new ArrayList<>();
                while (index>=0){
                    list.add(index);
                    index = big.indexOf(smalls[i],index+1);
                }
                result[i] = parseList2Array(list);
            }else {
                result[i] = new int[0];
            }
        }
        return result;
    }

    private int[] parseList2Array(List<Integer> list){
        int [] index = new int[list.size()];
        for (int i = 0; i < list.size() ; i++) {
            index[i] = list.get(i);
        }
        return index;
    }
}
复制代码

题很简答，但是我越刷越开心，又刷到了这样一题。

给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复，J 和 S 中的所有字符都是字母。字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

示例 1:

输入: J = "aA", S = "aAAbbbb"
输出: 3
复制代码

示例 2:

输入: J = "z", S = "ZZ"
输出: 0
复制代码

注意:

S 和 J 最多含有50个字母。
J 中的字符不重复。

我直接一波惯性思维，想到了 indexOf 真香(主要简单)，把 J 拆成 char[] ,那每个 char[i] ,不就相当于上一题里面的 small[i] 吗，这样一想，其实还是在母串里找每个字符出现的次数。

    public int numJewelsInStones(String J, String S) {
        int result = 0;
        char[] charArray = J.toCharArray();
        for (char item: charArray) {
            int index = S.indexOf(item);
            while (index>=0){
                result++;
                index = S.indexOf(item,index+1);
            }
        }
        return result;
    }
复制代码

解答出来之后，我就开始思考有没有其他方法可以更简单或者更快的解决这个题目。还是从刚刚这个思路切入，把 J 切成 char[] ，因为S中的 char[i] 可能是多个，所以还需要像上一题这样多次搜索，但是J中的元素是不会重复的，如果把 S 拆成 char[] ，那么对应可以直接在 J 中进行一次搜索，而且因为不需要取索引值，所以可以直接用 J.contains(char[i]) ，看返回的布尔值，实现计数。

    public int numJewelsInStones(String J, String S) {
        int result = 0;
        char[] charArray = S.toCharArray();
        for (char item: charArray) {
            if(J.contains(item+"")){
                result++;
            }
        }
        return result;
    }

复制代码

进一步思考，既然 J 的每个元素都不相同，那么我们可以采用元素都不重复的集合Set来存储J的每一个元素。不过这样需要对两个字符串都转数组，虽然简单但是感觉不如上述代码简洁。。。

        public int numJewelsInStones(String J, String S) {
        int result = 0;
        HashSet<Character> set = new HashSet<>();
        char[] chars = J.toCharArray();
        for (char item: chars) {
            set.add(item);
        }
        for (int i = 0; i < S.length(); i++) {
            if(set.contains(S.charAt(i)))
                result++;
        }
        return result;
    }
复制代码

写完这些，是不是突然发现，既然是用J中的每一个字符去挨个遍历 S 中的每一个字符。那么最粗暴的方法当然是双重 for 循环。

    public int numJewelsInStones(String J, String S) {
        int result = 0;
        for(char Jitem : J.toCharArray()){
            for(char Sitem : S.toCharArray()){
                if(Jitem == Sitem){
                    result++;
                }
            }
        }
        return result;
    }
复制代码

上述方法虽然简单，但是这样效率极低极低，这样的写法相当于是把整个 J 和整个 S 都遍历了一遍，相当于执行了 J.length*S.length 次。因为这里 J 的每一个字符都是唯一不重复的。那么我们可以用S去匹配J,找到自己break当前小循环直接进入下一次大循环，就会少一些遍历 J 中剩下的字符次数，相对而言就会少执行很多次循环体。

    public int numJewelsInStones(String J, String S) {
            int result = 0;
            for(char Sitem : S.toCharArray()){
                for(char Jitem : J.toCharArray()){
                    if(Jitem == Sitem){
                        result++;
                        break;
                    }
                }
            }
            return result;
        }
复制代码

结语

今天能偷闲多刷几题，题量不是越多越好，能通过自己刷的题举一反三才是硬道理。本文正在参与「掘金 2021 4 月刷题打卡」, 点击查看活动详情。喜欢的话点个赞吧。