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 "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []
s = "barfoothefoobarman"
words = ["foo", "bar"]
单词长度: wordLen = 3
单词个数: wordNum = 2
字符串长度: len = 17
Words Map = {[foo:1], [bar:1]}
i=0
子串 Map = {}
| b a r f o o t h e f o o b a r m a n
当前子串: "barfoo", 满足条件, res=[0]
i=1
子串 Map = {}
b | a r f o o t h e f o o b a r m a n
当前子串: "arfoot", 不满足条件, 退出, 移到下一个, res=[0]
i=2
子串 Map = {}
b a | r f o o t h e f o o b a r m a n
当前子串: "rfooth", 不满足条件, 退出, 移到下一个, res=[0]
.
.
.
i=9
子串 Map = {}
b a r f o o t h e | f o o b a r m a n
当前子串: "foobar", 满足条件, res=[0, 9]
.
.
.
i=13, 退出, 剩余子串长度不满足. res=[0, 9]
class ConcateSubstringWithAllWords {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
if (s == null || words == null || s.length() < words.length || words.length == 0) return res;
Map<String, Integer> wordsMap = new HashMap<>();
for (String w : words) {
wordsMap.put(w, wordsMap.getOrDefault(w, 0) + 1);
}
int len = s.length();
int wordNum = words.length;
int wordLen = words[0].length();
if (len < wordNum * wordLen) return res;
for (int i = 0; i < len - wordNum * wordLen + 1; i++) {
Map<String, Integer> subMap = new HashMap<>();
int currCount = 0;
while (currCount < wordNum) {
String currWord = s.substring(currCount * wordLen + i, (currCount + 1) * wordLen + i);
if (!wordsMap.containsKey(currWord)) break;
subMap.put(currWord, subMap.getOrDefault(currWord, 0) + 1);
if (subMap.get(currWord) > wordsMap.get(currWord)) break;
currCount++;
}
if (currCount == wordNum) {
res.add(i);
}
}
return res;
}
}
解法二
class ConcateSubstringWithAllWords {
public static List<Integer> findSubstring2(String s, String[] words) {
// basic cases
if (s == null || words == null || s.length() < words.length || words.length == 0) return res;
List<Integer> res = new ArrayList<>();
final Map<String, Integer> wordsMap = new HashMap<>();
for (final String word : words) {
wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
}
final int len = s.length();
final int wordNum = words.length;
final int wordLen = words[0].length();
for (int i = 0; i < wordLen; i++) {
int l = i, count = 0;
final Map<String, Integer> subMap = new HashMap<>();
for (int r = i; r <= len - wordLen; r += wordLen) {
final String word = s.substring(r, r + wordLen);
// 1. 不满足条件,直接跳到单词后面, 清空map
if (!wordsMap.containsKey(word)) {
subMap.clear();
count = 0;
l = r + wordLen;
continue;
}
subMap.put(word, subMap.getOrDefault(word, 0) + 1);
if (subMap.get(word) <= wordsMap.get(word)) {
count++;
} else {
// 2. 满足条件, 当时个数超过, 那么往前移动直到个数满足的index
while (subMap.get(word) > wordsMap.get(word)) {
final String first = s.substring(l, l += wordLen);
subMap.put(first, subMap.getOrDefault(first, 0) - 1);
if (subMap.get(first) < wordsMap.getOrDefault(first, 0)) {
count--;
}
}
}
if (count == wordNum) {
res.add(l);
count--;
final String first = s.substring(l, l += wordLen);
subMap.put(first, subMap.get(first) - 1);
}
}
}
return res;
}
}
from typing import List
import collections
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not s or not words:
return []
w_num = len(words)
w_len = len(words[0])
w_count = collections.Counter(words)
res = []
for i in range(w_len):
temp_count = collections.defaultdict(int)
left = i
for right in range(i, len(s) - w_len + 1, w_len):
temp_word = s[right: right + w_len]
if w_count[temp_word] > 0:
temp_count[temp_word] += 1
while temp_count[temp_word] > w_count[temp_word]:
temp_count[s[left: left + w_len]] -= 1
left += w_len
if right + w_len - left == w_num * w_len:
res.append(left)
temp_count[s[left: left + w_len]] -= 1
left += w_len
else:
left = right + w_len
temp_count.clear()
return res
