题意:给定一个字符串s和一组单词,每个单词长度一致,这些单词可以组成一个字符串称为
concatenated substring
,找出s中所有这些字符串的开始下标。
30. Substring with Concatenation of All Words (opens new window)
# 解法 1:哈希表
建立一个hashmap词典,key是string,value是integer,表示某个单词出现的次数。遍历字符串s,如果遇到词典中的单词则减一,直到全部减到0,表示存在一个符合要求的子串。
设a=单词数量,b=单词长度,n=字符串s的长度。
时间复杂度O(a+nab),空间复杂度O(a+b)。
class Solution {
private HashMap<String, Integer> wordMap = new HashMap<>();
private int substringLength;
private int wordCount;
private int wordLength;
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> indexes = new ArrayList<>();
wordCount = words.length;
wordLength = words[0].length();
substringLength = wordCount * wordLength;
for (int i = 0; i < wordCount; i++) {
wordMap.put(words[i], wordMap.getOrDefault(words[i], 0) + 1);
}
int fullLength = s.length();
// 遍历字符串找出所有可能的子串
for (int i = 0; i < fullLength + 1 - substringLength; i++) {
if (canfindSubstring(s, i)) {
indexes.add(i);
}
}
return indexes;
}
private boolean canfindSubstring(String s, int index) {
// 新建一个词典
HashMap<String, Integer> map = new HashMap<>(wordMap);
int wordsUsed = 0;
for (int i = index; i < index + substringLength; i+= wordLength) {
String word = s.substring(i, i + wordLength);
// 统计词典中单词出现的次数,遇到则减一
int remain = map.getOrDefault(word, 0);
if (remain > 0) {
wordsUsed++;
map.put(word, remain - 1);
} else {
break;
}
}
return wordsUsed == wordCount;
}
}
# 解法 2:滑动窗口
在上一个解法中在遍历过程中存在着大量重复计算,因此效率较低。处理字符串遍历问题时,可以使用滑动窗口加速。
左右指针从最左边开始,之前遍历时移动数是1,其实词典里的单词长度一致,可以改为和单词长度相同。
先移动右指针,如果单词不在词典里,那么在接下来的范围里是不可能找到子串的,所以可以移动左指针,跳过这个单词,重置窗口。如果单词在词典里,记录下这个单词的出现次数和总单词数。当次数到达词典里的单词次数时且没有重复单词出现时,记录左指针的下标。当出现重复单词时,移动右指针已没有意义,需要移动左指针,直到把重复单词删除。当左右指针宽度到达窗口宽度,也需要移动左指针。移动左指针后,需要判断最左边去掉的单词是否是重复的,该单词出现次数减一后和词典中的单词次数比较,如果小于说明是必要的,总单词数减一,否则说明是重复单词,去掉后窗口内就没有重复单词了。
因为下标跳跃改为单词长度,可能出现xfoobar
,[foo,bar]
这种情况,所以需要在滑动窗口外层再包一层循环。
设a=单词数量,b=单词长度,n=字符串s的长度。
空间复杂度O(a+b),时间复杂度O(a+b*n)。
l = 左指针,r = 右指针
不存在单词
foobarthefoobar => foobarthefoobar
| | |
l r l
r
重复单词和到达窗口宽度
foobarbarfoo => foobarbarfoo
| | | |
l r l r
class Solution {
private HashMap<String, Integer> wordMap = new HashMap<>();
private int wordLength;
private int wordCount;
private int sLength;
private int substringLength;
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> indexes = new ArrayList<>();
wordLength = words[0].length();
wordCount = words.length;
sLength = s.length();
substringLength = wordLength * wordCount;
for (int i = 0; i < wordCount; i++) {
wordMap.put(words[i], wordMap.getOrDefault(words[i], 0) + 1);
}
for (int i = 0; i < wordLength; i++) {
HashMap<String, Integer> wordsFound = new HashMap<>();
int wordsUsed = 0;
boolean isExcessWord = false;
int left = i;
for (int right = left; right < sLength + 1 - wordLength; right += wordLength) {
String word = s.substring(right, right + wordLength);
if (!wordMap.containsKey(word)) {
wordsFound.clear();
wordsUsed = 0;
isExcessWord = false;
left = right + wordLength;
} else {
while (right - left == substringLength || isExcessWord) {
String leftWord = s.substring(left, left + wordLength);
left += wordLength;
wordsFound.put(leftWord, wordsFound.get(leftWord) - 1);
if (wordsFound.get(leftWord) >= wordMap.get(leftWord)) {
isExcessWord = false;
} else {
wordsUsed--;
}
}
wordsFound.put(word, wordsFound.getOrDefault(word, 0) + 1);
if (wordsFound.get(word) <= wordMap.get(word)) {
wordsUsed++;
} else {
isExcessWord = true;
}
if (wordsUsed == wordCount && !isExcessWord) {
indexes.add(left);
}
}
}
}
return indexes;
}
}