leetcode 30. 串联所有单词的子串(优质解法)

2023-12-13 04:32:46

代码:

class Solution {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> integerList=new ArrayList<>();

        int length=words.length;    //words 数组中的字符串个数
        int size=words[0].length(); //words 数组中每个字符串的长度

        HashMap<String,Integer> hashMap1=new HashMap<>();   //存储 words 数组中字符串以及出现的个数


        //把 words 数组中字符串以及出现的个数保存到 hashMap1 中
        for(String str:words){
            hashMap1.put(str,hashMap1.getOrDefault(str,0)+1);
        }

        for(int i=0;i<size;i++){
            int count=0;    //记录当前子串中符合条件的字符串
            HashMap<String,Integer> hashMap2=new HashMap<>();   //存储讨论的子串中字符串以及出现的个数
            for(int left=i,right=i;right+size<=s.length();right+=size){
                //把 right 指针指向的数据入窗口
                String in=s.substring(right,right+size);
                hashMap2.put(in,hashMap2.getOrDefault(in,0)+1);

                //判断当前入窗口的字符串是否是符合条件的
                if(hashMap2.get(in)<=hashMap1.getOrDefault(in,0)){
                    count++;
                }

                //判断当前子串的长度是否过长,是否需要出窗口
                if(right-left+1>length*size){
                    String out=s.substring(left,left+size);
                    //判断出窗口的字符串是否是有效字符串
                    if(hashMap2.get(out)<=hashMap1.getOrDefault(out,0)){
                        count--;
                    }
                    hashMap2.put(out,hashMap2.get(out)-1);
                    left+=size;
                }

                //判断有效字符串个数是否符合条件
                if(count==length){
                    integerList.add(left);
                }
            }
        }
        return integerList;
    }
}

题解:

? ? ? ? 本题的含义表达得很明确,我们需要在字符串 s 中找到一个子串,子串由字符串数组 words 中的字符串以不同顺序组成

? ? ? ? 我们首先可以想到一个暴力解法,遍历出字符串 s 中的所有子串,找出完全由 words 中的字符串以不同顺序组成的子串。现在就涉及到一个问题,我们如何知道子串是完全由 words 中的字符串以不同顺序组成的

? ? ? ? 我们可以利用哈希表 hash1 和 hash2 存储 words 数组中和子串中字符串的相关信息,以字符串为 key ,个数为 value ,然后比对 hash1 和 hash2 中的内容,便知道当前子串是否是符合条件的

? ? ? ? 假设输入:s = "barfoothefoobar", words = ["foo","bar"]

? ? ? ? 首先我们可以获得的信息是,words 数组中的字符串个数 length = 2,每个字符串的大小 size = 3 ,由于我们要遍历所有的子串,所以让 L 和 R 指针指向下标为 0 的位置。我们将 words 数组中的相关信息保存到哈希表 hash1 中,foo-1,bar-1用变量 count 记录子串中有效字符串的个数

????????? 因为符合要求的子串是由 words 数组中的字符串按不同顺序组成的,而 words 数组中的字符串是 3 个字符为一个整体,所以我们在寻找子串的时候也以 3 个字符为一个整体,R 指针指向当前位置,通过?s.substring(right,right+size) 取出字符串 bar,将 bar - 1 保存到 hash2 中,由于在hash1 中 bar-1,只要子串中的字符个数小于等于 wors 数组中对应字符的个数,就代表该字符是有效字符,所以 bar 是有效字符,此时 count++,count=1

b????????a????????r????????f????????o????????o????????t????????h????????e????????f????????o????????o????????b????????a????????r? ? ??

L

R

? ? ?录入字符串 bar 的信息以后,R 指针向右移动 size 位,录入下一个字符串 foo,将 foo- 1 保存到 hash2 中,由于在hash1 中 foo-1,,所以 foo 是有效字符,此时 count++,count=2,因为此时子串为 barfoo 长度为 6 == size*length ,并且 count == 2 == length,所以该子串是符合要求的,我们就直接记录 L 指针指向的下标 0

b????????a????????r????????f????????o????????o????????t????????h????????e????????f????????o????????o????????b????????a????????r? ? ??

L

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?R??

? ? ? ? 当 R 指针再向右移 size 位以后,子串为 barfoothe,大小为 9 > size * length ,字符数都比 words 数组中的字符数多了,肯定不符合要求,代表以 L 指针为首的子串已经讨论完毕,让 L 指针向右移动 size 位,讨论下一组字符串

b????????a????????r????????f????????o????????o????????t????????h????????e????????f????????o????????o????????b????????a????????r? ? ??? ? ?

L

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?R? ? ?? ?

? ? ? ? L 指针之前指向的是字符串 bar ,bar 在 hash2 中的个数为 1,小于等于在 hash1 中的个数,所以是有效字符串,因此在将 L 指针移动前,我们需要修改?hash2 中的 bar - 0,count = 1,

此时子串的长度符合要求,但是有效字符串个数 count < length,所以该子串不符合要求,让 R 指针向右移动 size 位?

b????????a????????r????????f????????o????????o????????t????????h????????e????????f????????o????????o????????b????????a????????r? ? ??? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? L??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?R?

? ? ? ? 之后循环上述操作即可

? ? ? ? 有细心的小伙伴会发现,上面的流程没有讨论完所有的子串,我们还需要以如下的两种情况,继续上述的操作,也就是在上述的循环操作要执行 size 次

b????????a????????r????????f????????o????????o????????t????????h????????e????????f????????o????????o????????b????????a????????r? ? ??? ? ?

???????????L

? ? ? ? ? ?R

? ??

b????????a????????r????????f????????o????????o????????t????????h????????e????????f????????o????????o????????b????????a????????r? ? ??? ? ?

????????????????????L

? ? ? ? ? ??????????R

? ????

文章来源:https://blog.csdn.net/q322359/article/details/134944265
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。