来源:力扣(LeetCode)
给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配,中间不能有其他字符 ,但不需要考虑 words 中单词串联的顺序。
示例 1:
输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2:
输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]
示例 3:
输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]
提示:
1 <= s.length <= 104
s
由小写英文字母组成 1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i]
由小写英文字母组成
wordsMap
保存word的字符串值为出现次数num
和第一个元素的字符串长度len
(因为题目说每个单词长度相等,所以获取第一个就可以了)tempMap
,元素跟tempMap
相同,然后开始遍历字符串,每次遍历都清空tempMap
,并重新加wordsMap
的元素num*len
长度的字符串,再截取每个元素len
的长度判断是否再tempMap
中,如果有,次数-1,-1后小于就remove掉,如果最后tempMap
的size
为0,那么这个就是一个吻合的字符串,保存下标class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
//如果为空,直接结束
if (s.length() == 0 || words.length == 0) return res;
//第一个元素字符串长度
int len = words[0].length();
//数组长度
int num = words.length;
//保存所有单词,用于判断字符串是否相等
HashMap<String, Integer> wordsMap = new HashMap<>();
for (String word : words) {
if(wordsMap.containsKey(word)){
wordsMap.put(word,wordsMap.get(word)+1);
continue;
}
wordsMap.put(word,1);
}
//同上,区别在于这个会remove操作
HashMap<String, Integer> tempMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
//清空map
tempMap.clear();
//添加wordsMap元素进去
tempMap.putAll(wordsMap);
//截取字符串的结束位置
int j = i + len * num;
//越界处理
if (j > s.length()) break;
String substr = s.substring(i, j);
for (int k = 0; k < substr.length(); k += len) {
if (k + len > substr.length()) break;
//截取单词长度的字符串
String tempStr = substr.substring(k, k + len);
//不吻合,终止循环
if (!tempMap.containsKey(tempStr)) {
break;
}
Integer count = tempMap.get(tempStr);
if(count - 1 <= 0){
tempMap.remove(tempStr);
continue;
}
tempMap.put(tempStr, count - 1);
}
//如果最后map为0,则完全匹配,记录开始下标
if (tempMap.size() <= 0) {
res.add(i);
}
}
return res;
}
}
这题虽然难度是 Hard,但是整体的实现和理解不是很难的。