30.substring-with-concatenation-of-all-words-cn
Last updated
Was this helpful?
Last updated
Was this helpful?
Was this helpful?
https://leetcode.com/problems/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 "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: []题意: 给定一个字符串(String s), 给定n个单词组成的字符串数组(String[] words), 找出所有子串(substring)的起始下标(start index), 使得该子串包含所有的单词, 每个单词的个数也要相同(子串中单词顺序任意).
先简单,直接,暴力的解 (暴力出奇迹, 😄).
遍历字符s,判断每个子串是匹配字符串数组中所有单词, 如果匹配, 记录下标 (index), 条件中每个单词的长度是相同的, 所以从当前下标, 可以很快得到单词长度的子串并进行比较.
由于不考虑顺序,这里可以用Hashmap先保存所有单词,并记录单词出现的次数. Map<Key, Value>- key 是单词, value 是单词的个数.
遍历字符s的时候,扫描并记录子串的单词和单词个数,用另一个HashMap保存, (key 是当前子串的单词, value 是当前子串单词出现的个数), 并与单词数组中单词和单词出现个数比较,
如果当前单词不在单词数组中,那么以当前字符开头的子串不可能满足情况, 提前结束, 往后移动到下一个字符的子串.
如果当前单词个数超过单词数组, 也不可能满足, 结束, 往后移动到下一个
满足的单词的数量(count)加1.
比较满足的单词数量(count == wordNum), 满足, 记录下当前下标(index), 移动到下一个字符
每次移动第二个HashMap清空, 重新计算
例子:
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]时间复杂度(TC): O(n * m) - n是s的长度, m是单词(words)的个数.
空间复杂度(SC): O(m)
参考 [shichaotan的解法](https://leetcode.com/problems/substring-with-concatenation-of-all-words/discuss/13656/An-O(N)-solution-with-detailed-explanation)
在解法一中,我们每次移动一个字符(char), 这样就造成了很多不必要的重复计算. 在解法二中,每次移动一个单词(word), 这样可以以word长度分类移动, 例如: word长度为3, 那么就可以分为3类来移动.
例子如下图, 对于单词(word)长度为3, 分为 i = 0, i = 1, i = 2 三类移动单词的距离.
从例子中,我们可以发现,按单词(word)移动,在解法一中,考虑了三种情况,那么解法二可以针对这三点进行优化:
当面单词不满足(不在给定单词数组(words)中).
当面单词出现在单词数组(words)中,但个数超过给定的个数
往后移动的过程,不需要每次都清空HashMap, 造成重复计算, 浪费资源.
对于1中单词不满足了, 可以略过(skip)掉不满足的这个单词前面所有的移动, 直接移动到下一个单词. 例如:
对于2中单词满足, 但是个数超过给定个数的情况,
这样就不需要每次移动都清空 HashMap, 而是当单词不满足的情况下, 清空HashMap 即可.
相较于解法一中, 每次移动一个字符都需要清空HashMap,节省很多时间的计算
时间复杂度(TC): O(n) - n 为 S 的长度
空间复杂度(SC): O(m) - m 为单词个数
解法一 - 暴力
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;
}
}Python code from @sunboman
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
