# 引言

题目链接:https://leetcode.com/problems/substring-with-concatenation-of-all-words/

# 题目大意

给出一个长字符串 s 和一个字符串数组 words, 返回由 words 中字符串拼接成的长字符串 (假设为 x) 在 s 中的索引集合 (x 由 words 中所有元素拼接而成,每一个元素都包含且只有一个)

Hint------------------
  1. words 中的每个字符串长度相等

  2. words 中的字符串可以重复 (自己脑补了一波,坑 skr 人 T_T)

  • Example
Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]

Output: [0,9]

Input:
 s = "wordgoodgoodgoodbestword"
 words = ["word","good","best","good"]

Output: [8]

# 题解

这个题目其实和 LeetCode 的第三题 Substring Without Repeating Characters 的解题思路核心是一样的,可以看看博主之前的题解 传送门 Click Here! 都是利用滑动窗口的思想。

来分析下两道题题目的区别,第三题求的是连续的最长的不包含重复字符的子串长度,这道题目求解由 words 中字符串拼接成的长字符串 x 在 s 中的索引位置集合。转换一下,就是 s 中查找连续的一段字符串 x, 这个字符串由 words 中所有字符串拼接而成,把所有符合条件的索引记录返回即可。 所以两者本质上是一致的。

由于本题 words 中所有字符串长度一致 (假设为 len), 所以可以把 len 当做一个整体。设定滑动窗口包含的子串由 words 中单词拼接而成 (当前从某个起点开始正在查询并且不断扩展的子串), 采取如下步骤解题

  1. 申明一个 hashmap, 用 words 中的字符串作为 key 在 words 中出现次数作为 value, 构建比对映射表。
  2. 设定当前滑动窗口左边界 lastDiffIndex, 初始为 0
  3. 申明一个 curhashmap 表示已经匹配查询列表,查询长度为 len 的子串 sub 在 hashmap 中是否存在
    1. 不存在:表明当前滑动窗口不符合规范,不能由 words 中所有字符串凭拼接构成,直接设置滑动窗口左边界为当前下标
    2. 存在:(1) curhashmap 中的键值对对应数量小于 hashmap 查询子串有效,滑动窗口左边界不变对应 curhashmap 对应键值数量加一,继续查询下一个长度为 len 的子串 sub, (2) curhashmap 中的键值对对应数量大于等于 hashmap 查询子串,无效,移动滑动窗口左边界每次加 len 的跨度,知道当前查询子串 sub 对应键值数量小于等于 hashmap

这样可以做到每次跨度为 words 中单个字符串长度 len, 为了能够遍历到所有单词组合,一般来说会选择双层循环外层每次 + 1 再次遍历,但是本题 words 中字符串长度一致,每次跨度都是 len, 所以只需要 + 1 往后偏移 len-1 次进行跨度为 len 的完全遍历即可覆盖 s 中的所有字符,因为再次偏移到 len 实际上已经进入了下一个周期循环完全重复。

因此本题采用双层循环,外层 i = [0-len] 跨度为 1, 内层 j = [i, lens-len] 跨度为 len, 每次截取长度为 [j,j+len] 之间的字符串判断,总遍历次数 为 len*n/len=n

# 复杂度

时间复杂度 O(n)

空间复杂度 O(km) , k 为给出的单词序列的长度,m 为序列中每个单词的长度

# AC 代码

c++ 版本

class Solution
{
  public:
    vector<int> findSubstring(string s, vector<string> &words)
    {
        // invalid
        if (s.length() <= 0 || words.size() <= 0)
        {
            return vector<int>{};
        }
        unordered_map<string, int> hashMap;
        unordered_map<string, int> curhashxMap;
        vector<int> ret;
        for (string word : words)
        {
            ++hashMap[word];
        }
        int lenS = s.length();
        int lenWord = words[0].length();
        int lens = words.size();
        int lastDiffIndex = 0;
        int count = 0;
        for (int i = 0; i < lenWord; ++i)
        {
            curhashxMap.clear();
            lastDiffIndex = i;
            count = 0;
            for (int j = i; j <= lenS - lenWord; j += lenWord)
            {
                string tmp = s.substr(j, lenWord);
                if (hashMap.count(tmp) <= 0)
                {
                    curhashxMap.clear();
                    lastDiffIndex = j + lenWord;
                    count = 0;
                    continue;
                }
                ++curhashxMap[tmp];
                ++count;
                if (curhashxMap[tmp] <= hashMap[tmp])
                {
                    if (lens == count)
                    {
                        ret.push_back(lastDiffIndex);
                        --curhashxMap[s.substr(lastDiffIndex, lenWord)];
                        --count;
                        lastDiffIndex += lenWord;
                    }
                }
                else
                {
                    while (curhashxMap[tmp] > hashMap[tmp])
                    {
                        --curhashxMap[s.substr(lastDiffIndex, lenWord)];
                        --count;
                        lastDiffIndex += lenWord;
                    }
                }
            }
        }
        return ret;
    }
};

go 版本

func findSubstring(s string, words []string) []int {
	lenS, lenWords := len(s), len(words)
	if 0 == lenS || 0 == lenWords {
		return nil
	}
	hashMap, curHashMap := make(map[string]int), make(map[string]int)
	var ret []int
	lenword := len(words[0])
	for _, v := range words {
		hashMap[v]++
	}
	for i := 0; i < lenword; i++ {
		curHashMap = make(map[string]int)
		lastDiffIndex, count := i, 0
		for j := i; j <= lenS-lenword; j += lenword {
			tmp := s[j : j+lenword]
			if _, ok := hashMap[tmp]; false == ok {
				curHashMap = make(map[string]int)
				lastDiffIndex, count = j+lenword, 0
				continue
			}
			curHashMap[tmp]++
			count++
			if curHashMap[tmp] <= hashMap[tmp] {
				if lenWords == count {
					ret = append(ret, lastDiffIndex)
					curHashMap[s[lastDiffIndex:lastDiffIndex+lenword]]--
					count--
					lastDiffIndex += lenword
				}
			} else {
				for curHashMap[tmp] > hashMap[tmp] {
					curHashMap[s[lastDiffIndex:lastDiffIndex+lenword]]--
					count--
					lastDiffIndex += lenword
				}
			}
		}
	}
	return ret
}
更新于 阅读次数