【算法】串联所有单词的子串

一、题目

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

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

示例 1：

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

示例 2：

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

二、题解

题目 :给定一个字符串 s 和一些长度相同的单词 words。

题目解读：

• 参数一个String类型的数组，一个字符串

• words的每个长度都相等。

• 数组中的几个值任意组合，然后在字符串中找到对应的下标。

• 返回一个下标组成的list

解体方法

• 用一个map记录words中的单词各有多少个
• 每个word的单词长度为len,所有单词的总长度allLen
• s中依次截取allLen的字符串，然后以len长度分割单词，每个单词记录到tempMap中
• 比较map和Map是不是相等

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new LinkedList<Integer>();//用来记录结果
        Map<String, Integer> map = new HashMap<String,Integer>();//用来记录words中的每个单词，以及单词的长度
        if(words.length==0||s==null||"".equals(s))return result;//基础判断
        int len = words[0].length();//每个单词的长度
        int allLen = len*words.length;//所有单词拼接起来的总长度
        if(s.length()<allLen)return result;
        for(int i=0;i<words.length;i++) {
            map.put(words[i],map.getOrDefault(words[i], 0)+1);
        }
        //
        for(int i=0;i<s.length()-allLen+1;i++) {//s中依次截取allLen的字符串
            Map<String, Integer> tempMap = new HashMap<String,Integer>();
            for(int j =0;j<allLen;j+=len) {//截取每个单词
                String tempWrod = s.substring(i+j,i+j+len);
                tempMap.put(tempWrod,tempMap.getOrDefault(tempWrod, 0)+1);//单词进入map
            }
            if(map.equals(tempMap)){result.add(i);}//
        }
        return result;
    }
}