文章目录

• 题目描述
• 解题方法
• • 滑动窗口
  • • java代码
    • 复杂度分析
    • 相似题目

      题目描述

      给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

      s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

      例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

      返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

      示例 1：

      输入：s = "barfoothefoobarman", words = ["foo","bar"]
      输出：[0,9]
      解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
      子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
      子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
      输出顺序无关紧要。返回 [9,0] 也是可以的。
      

      示例 2：

      输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
      输出：[]
      解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
      s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
      所以我们返回一个空数组。
      

      示例 3：

      输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
      输出：[6,9,12]
      解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
      子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
      子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
      子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
      

      提示：

      • 1 <= s.length <= 10⁴
      • 1 <= words.length <= 5000
      • 1 <= words[i].length <= 30

        words[i] 和 s 由小写英文字母组成

        解题方法

        滑动窗口

        题目中说了words 中所有字符串 长度相同，这样我们就可以用滑动窗口每次扩充words[0].length()的步长，匹配words中的字符串来控制滑动窗口的大小。当滑动窗口的字符串数量与words中的字符串数量匹配时，则将滑动窗口的左边界加入结果集。

        java代码

        public List findSubstring(String s, String[] words) {
            List list = new ArrayList<>();
            if (s == null || s.length() == 0 || words == null || words.length == 0) {
                return list;
            }
            int size = words[0].length();
            int len = words.length;
            // 记录words数组中字符串的map，key是字符串，value是字符串出现次数
            Map map = new HashMap<>();
            // 记录当前遍历的字符串s中匹配words数组中字符串的map，简称为滑动窗口map，key是字符串，value是字符串出现次数
            Map curMap = new HashMap<>();
            for (int i = 0; i < len; i++) {
                map.put(words[i], map.getOrDefault(words[i], 0) + 1);
            }
            // s字符串以 0 ~ size - 1为起点，每次匹配size个字符
            for (int i = 0; i < size; i++) {
                // 当前curMap字符串数量
                int count = 0;
                // 滑动窗口左边界
                int start = i;
                // 每次匹配size个字符
                for (int j = i; j <= s.length() - size; j += size) {
                    String cur = s.substring(j, j + size);
                    // words中有cur这个字符串
                    if (map.containsKey(cur)) {
                        curMap.put(cur, curMap.getOrDefault(cur, 0) + 1);
                        count++;
                        // 当cur出现的次数大于words中的次数时，一直移动滑动窗口左边界，直到左边界出掉一个cur字符串
                        while (curMap.get(cur) > map.get(cur)) {
                            String left = s.substring(start, start + size);
                            curMap.put(left, curMap.get(left) - 1);
                            start = start + size;
                            count--;
                        }
                        // 匹配的字符串数量与words中的字符串数量相等，将滑动窗口左边界加入结果集，滑动窗口左边界往后移动size
                        if (count == len) {
                            list.add(start);
                            String left = s.substring(start, start + size);
                            curMap.put(left, curMap.get(left) - 1);
                            start = start + size;
                            count--;
                        }
                    } else {
                        // words中没有匹配字符串，清理滑动窗口，滑动窗口左边界移动到下一个字符串开始位置
                        curMap.clear();
                        start = j + size;
                        count = 0;
                    }
                }
                curMap.clear();
            }
            return list;
        }
        

        复杂度分析

        时间复杂度： O ( l × n ) O(l \times n) O(l×n)， l l l 是字符串 s s s 的长度， n n n 是 w o r d s words words 中每个单词的长度。因为要遍历 s s s 字符串 l × n l \times n l×n次。

        空间复杂度： O ( m × n ) O(m \times n) O(m×n)， m m m 是 w o r d s words words 中单词个数， n n n 是 w o r d s words words 中每个单词的长度。需要用哈希表存储单词的出现频率。

        相似题目

        [leetcode] 3. 无重复字符的最长子串

        ---

        • 个人公众号

          

        • 个人小游戏

          

         
         东营网站建设制作  网站设计图片成品  企业营销管理  建设官网登录  app源码  html网页制作报告书