前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【力扣刷题】30. 串联所有单词的子串

【力扣刷题】30. 串联所有单词的子串

作者头像
jayjay
发布2022-11-02 16:54:37
2160
发布2022-11-02 16:54:37
举报
文章被收录于专栏:jay_blogjay_blog

一、题目描述

来源:力扣(LeetCode)

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配,中间不能有其他字符 ,但不需要考虑 words 中单词串联的顺序。

示例 1:

代码语言:javascript
复制
输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2:

代码语言:javascript
复制
输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]

示例 3:

代码语言:javascript
复制
输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]

提示:

1 <= s.length <= 104 s 由小写英文字母组成 1 <= words.length <= 5000 1 <= words[i].length <= 30 words[i] 由小写英文字母组成

二、思路分析

  1. 用一个map wordsMap保存word的字符串值为出现次数
  2. 获取到数组的长度num和第一个元素的字符串长度len(因为题目说每个单词长度相等,所以获取第一个就可以了)
  3. 创建一个临时map tempMap,元素跟tempMap相同,然后开始遍历字符串,每次遍历都清空tempMap,并重新加wordsMap的元素
  4. 截取num*len长度的字符串,再截取每个元素len的长度判断是否再tempMap中,如果有,次数-1,-1后小于就remove掉,如果最后tempMapsize为0,那么这个就是一个吻合的字符串,保存下标
  5. 进行下一轮循环。直到超出边界

三、代码实现

代码语言:javascript
复制
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
      List<Integer> res = new ArrayList<>();
        //如果为空,直接结束
        if (s.length() == 0 || words.length == 0) return res;
        //第一个元素字符串长度
        int len = words[0].length();
        //数组长度
        int num = words.length;
        //保存所有单词,用于判断字符串是否相等
        HashMap<String, Integer> wordsMap = new HashMap<>();
        for (String word : words) {
            if(wordsMap.containsKey(word)){
                wordsMap.put(word,wordsMap.get(word)+1);
                continue;
            }
            wordsMap.put(word,1);
        }
        //同上,区别在于这个会remove操作
        HashMap<String, Integer> tempMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            //清空map
            tempMap.clear();
            //添加wordsMap元素进去
            tempMap.putAll(wordsMap);
            //截取字符串的结束位置
            int j = i + len * num;
            //越界处理
            if (j > s.length()) break;
            String substr = s.substring(i, j);
            for (int k = 0; k < substr.length(); k += len) {
                if (k + len > substr.length()) break;
                //截取单词长度的字符串
                String tempStr = substr.substring(k, k + len);
                //不吻合,终止循环
                if (!tempMap.containsKey(tempStr)) {
                    break;
                }
                Integer count = tempMap.get(tempStr);
                if(count - 1 <= 0){
                    tempMap.remove(tempStr);
                    continue;
                }
                tempMap.put(tempStr, count - 1);

            }
            //如果最后map为0,则完全匹配,记录开始下标
            if (tempMap.size() <= 0) {
                res.add(i);
            }
        }
        return res;
    }
}

四、运行结果

image.png
image.png

总结

这题虽然难度是 Hard,但是整体的实现和理解不是很难的。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-03-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目描述
  • 二、思路分析
  • 三、代码实现
  • 四、运行结果
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档