这是我参与更文挑战的第27天，活动详情查看：更文挑战

前言

力扣第三十题 串联所有单词的子串 如下所示：.

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

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

示例 1：

输入：s = “barfoothefoobarman”, words = [“foo”,”bar”]
输出：[0,9]
解释：从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]
输出：[]

示例 3：

输入：s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]
输出：[6,9,12]

一、思路

题目中有两个比较重要的信息：长度相同的单词和不需要考虑单词的串联顺序

我用哈希表照着题目的思路实现了，但是击败率不是很理想。所以又看了一下力扣上面使用滑动窗口 + 哈希表可以有效优化，击败率可以达到98%。在看了别人的题解后，准备自己实现一个简短一点的方式，还没有AC，等后面实现了再放方案二吧。

这里主要说一下使用哈希表来实现，大概的步骤如下所示：

每次遍历前将words中的单词放入到哈希表中
判断从当前位置开始后的字符串是否能够完全匹配 words 中的单词，如果可以完全匹配则加入到结果

举个例子

如果key中再map中存在，则让 value -1

以示例1 为例子，介绍一下以 i=0 为起点的情况

新建一个哈希表 map，key 为单词，value 为单词出现的次数。此处的结果为 {'foo': 1; 'bar': 1}
从字符串中取一个单词的长度 bar,更改 map，此时 bar -> 0。
在取一个单词的长度 foor，更改 map，此时 foor -> 0。
可以匹配，结果集 ret中加入 0
其它位置的判断均类似

二、实现

实现代码

变量解释
len：单词数组长度
wordLen：单词长度
map：临时哈希表，value为单词出现次数

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        int len = words.length; // 数组长度
        int wordLen = words[0].length();
        for (int i=0; i< s.length() - len * wordLen + 1; i++)  {
            Map<String, Integer> map = new HashMap<>();
            // 放入HashMap中
            for (String word : words) {
                map.merge(word, 1, Integer::sum);
            }
            for (int j=0; j < len; j++) {
                String word = s.substring(i + j * wordLen, i + (j+1) * wordLen);
                if (map.containsKey(word) && map.get(word) > 0) {
                    map.merge(word, -1, Integer::sum);
                    if (j == len -1) {
                        ret.add(i);
                    }
                } else {
                    break;
                }
            }
        }
        return ret;
    }
复制代码

测试代码

    public static void main(String[] args) {
        String[] words = {"word","good","best","good"};
        new Number30().findSubstring("wordgoodgoodgoodbestword", words);
    }
复制代码