博文中会简要介绍Leetcode P0030题目分析及解题思路。
“Substring with Concatenation of All Words”是一道比较难的题目，考察的重点主要是滑动窗口的思想。除此之外，代码实现的各种细节也需要重点关注。
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Example 1:
Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively. The output order does not matter, returning [9,0] is fine too.
这道题的解决思路相对比较明显，核心思路是滑动窗口。为了控制窗口内合法，使用HashTable来记录窗口内出现的合法word的个数，准确地说是记录合法word的剩余个数，即还需要多少个才能满足words数组内的全部字符串都出现在窗口内。
这样一来，一旦发现HashTable里给定word的键的值减去1以后小于0，则可以认为若包含该word，则窗口不合法，需要移动窗口左端指针直到跳过该word，这里“跳过该word”可以是当前的word的位置，也可以是前缀序列中某个相同word的位置，因为不合法有两种情况，一是该word不属于数组内，二是该word在前缀序列中已经出现过足够多次，不能再出现了，前者即跳过当前word，后者则是跳过前缀序列中第一次出现的与当前相同的word。
若窗口内完全合法，即包含了words数组中全部字符串，则记录起点位置，并且将起点后移一个word长度，复原HashTable后，重新再移动右指针，这样能保证选取到全部合法的起点。
在移动左指针的时候，需要注意的是复原HashTable，即将HashTable里的键的值还原。具体的细节可以参照下面代码内的注释。
以下是Java的题解代码实现。
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
if (words == null || words.length == 0)
return new ArrayList<>();
int wordLen = words[0].length(), counter = 0;
Map<String, Integer> word2CountMap = new HashMap<>();
for (String word: words) {
++counter;
word2CountMap.put(word, word2CountMap.getOrDefault(word, 0)+1);
}
if (s.length() < counter*wordLen)
return new ArrayList<>();
List<Integer> indices = new ArrayList<>();
for (int i1=0; i1<wordLen; ++i1) {
int start = i1, count = counter;
int right = start;
while (start <= s.length()-counter*wordLen) {
String word = s.substring(right, right+wordLen);
while (count > 0 && word2CountMap.getOrDefault(word, 0)-1 >= 0) {
word2CountMap.put(word, word2CountMap.get(word)-1);
--count;
right += wordLen;
if (right+wordLen > s.length())
break;
word = s.substring(right, right+wordLen);
}
if (count == 0) {
indices.add(start);
// 移除最开头的word（temp），复原HashTable和计数器count
String temp = s.substring(start, start+wordLen);
word2CountMap.put(temp, word2CountMap.get(temp)+1);
++count;
// 起点后移
start += wordLen;
}
else {
// 若右指针超出数组范围，则说明该start下不存在合法解
if (right+wordLen > s.length())
break;
int left = start;
String temp = s.substring(left, left+wordLen);
// 从开头开始逐个移除word（temp），并复原HashTable和计数器count，直到和当前word相同的word（temp）
while (!temp.equals(word)) {
word2CountMap.put(temp, word2CountMap.get(temp)+1);
++count;
left += wordLen;
temp = s.substring(left, left+wordLen);
}
// 起点后移
start = left+wordLen;
right += wordLen;
}
}
// 完全复原HashTable
while (start < right) {
String temp = s.substring(start, start+wordLen);
word2CountMap.put(temp, word2CountMap.get(temp)+1);
start += wordLen;
}
}
return indices;
}
}
以下是第二种Java的题解代码实现，具有相同思路，但是写法不同。
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
if (words == null || words.length == 0)
return new ArrayList<>();
int wordLen = words[0].length(), counter = 0;
Map<String, Integer> word2CountMap = new HashMap<>();
for (String word: words) {
++counter;
word2CountMap.put(word, word2CountMap.getOrDefault(word, 0)+1);
}
if (s.length() < counter*wordLen)
return new ArrayList<>();
List<Integer> indices = new ArrayList<>();
for (int i1=0; i1<wordLen; ++i1) {
int start = i1, count = counter;
int right = start;
while (start <= s.length()-counter*wordLen) {
String word = "";
while (count > 0 && right+wordLen <= s.length()
&& word2CountMap.getOrDefault(word, 0) >= 0) {
// 获取当前word
word = s.substring(right, right+wordLen);
word2CountMap.put(word, word2CountMap.getOrDefault(word, 0)-1);
// 更新计数器count
if (word2CountMap.get(word) >= 0)
--count;
// 移动右指针right
right += wordLen;
}
if (count == 0) {
indices.add(start);
// 移除最开头的word（temp），复原HashTable和计数器count
String temp = s.substring(start, start+wordLen);
word2CountMap.put(temp, word2CountMap.get(temp)+1);
++count;
// 起点后移
start += wordLen;
}
else {
// 若右指针超出数组范围，则说明该start下不存在合法解
if (right+wordLen > s.length())
break;
int left = start;
// 从开头开始逐个移除word（temp），并复原HashTable和计数器count，直到和当前word相同的word（temp）
while (word2CountMap.get(word) < 0) {
String temp = s.substring(left, left+wordLen);
word2CountMap.put(temp, word2CountMap.get(temp)+1);
// 当前temp是words里的单词
if (word2CountMap.get(temp) > 0)
++count;
left += wordLen;
}
// 起点后移
start = left;
}
}
// 完全复原HashTable
while (start < right) {
String temp = s.substring(start, start+wordLen);
word2CountMap.put(temp, word2CountMap.get(temp)+1);
start += wordLen;
}
}
return indices;
}
}