LeetCode_30: Substring with Concatenation of All Words

# 引言

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

# 题目大意

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

• 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
}