LeetCode 刷题记录30. Substring with Concatenation of All Words_seen[word] = seen[word] + 1 || 1
赞
踩
题目：
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: []
解法1：
暴力法：
让我们求串联所有单词的子串，就是说给定一个长字符串，再给定几个长度相同的单词，让我们找出串联给定所有单词的子串的起始位置，假设word数组中有num个单词，每个单词的长度为len，遍历s字符串，每次取出长度为num*len的子串，看是否与word数组中所有字符串的串联是否一致，注意word数组中各个字符串的顺序可以是任意的，比如说对于例1：可以是barfoo，也可以是foobar
所以通过map集合来记录各个字符串出现的次数来判断，如果一致就将起始位置加入目标数组
举例：
s = “wordgoodgoodgoodbestword”,
words = [“word”,“good”,“best”,“word”]
首先建立word数组的map（counts）： {“word” ：2，“good”：1，“best”：1}
i=0开始遍历，遍历到i = n - num * len = 8 结束 即剩下的字符串为 goodgoodbestword，再往下的字符串长度不满足num*len，不符合题意
为了方便比较，每次i循环过程中，另外建立一个map（seen），每次取长度为 len 的子串，看其是否是 words 中的单词，总共取num次。
i=0,第一个单词是word，在counts中存在，将seen中"word"映射值加1,map（seen）： {“word” ：1}
然后比较检测若其映射值超过counts 中的映射值，没超过证明是安全的
继续循环，第二个单词是good,在counts中存在，将seen中"word"映射值加1,map（seen）： {“word” ：1，“good”：1}
然后比较检测若其映射值超过counts 中的映射值，没超过证明是安全的
继续循环，第三个单词是good,在counts中存在，将seen中"word"映射值加1,map（seen）： {“word” ：1，“good”：2}
然后比较检测若其映射值超过counts 中的映射值，超过直接说明这不是我们需要的子串，直接跳出内层循环
i=1,第一个单词是ordg，在counts中不存在直接说明这不是我们需要的子串，直接跳出内层循环
如果内层循环结束后，检测了num次，说明是我们需要的子串，直接将起始位置i加入目标数组中
c++：
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> indexes; int n = s.size(); int num = words.size(); if(n == 0 || num == 0) return indexes; int len = words[0].size(); unordered_map<string, int> counts; for(string word : words) counts[word]++; for(int i = 0; i < n - num * len + 1; i++){ unordered_map<string, int> seen; int j = 0; for(; j < num; j++){ string word = s.substr(i + j * len, len); if(counts.find(word) != counts.end()){ seen[word]++; if(seen[word] > counts[word]) break; } else break; } if(j == num) indexes.push_back(i); } return indexes; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
java：
java中map和c++中不同，是没有默认值的，所以当我们去取一个不存在的键时会发生空指针异常，所以我们要使用getOrDefault(word, 0)给相应的键设默认值
class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> indexes = new ArrayList<>(); int n = s.length(); int num = words.length; if(n == 0 || num == 0 || s == null || words == null) return indexes; int len = words[0].length(); Map<String, Integer> counts = new HashMap<>(); for(String word : words) { // counts.put(word, counts.get(word) + 1); counts.put(word, counts.getOrDefault(word, 0) + 1); } for(int i = 0; i < n - num * len + 1; i++){ Map<String, Integer> seen = new HashMap<>(); int j = 0; for(; j < num; j++){ String word = s.substring(i + j * len, i + (j + 1) * len); if(counts.containsKey(word)){ seen.put(word, seen.getOrDefault(word, 0) + 1); if(seen.get(word) > counts.get(word)) break; } else break; } if(j == num) indexes.add(i); } return indexes; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
python：
使用collections.Counter来完成map中计数的任务Python标准库——collections模块的Counter类
Python和java一样，当我们去取一个不存在的键时会发生异常，有两种解决方案
- get(word, 0) 给予默认值
- 在初始化map时，使用defaultdict(int)而不是dict()，这样可以使用seen[word] += 1 python中defaultdict用法详解
Python3 取消了xrange，Python3中的range就是Python2的range
class Solution(object): def findSubstring(self, s, words): """ :type s: str :type words: List[str] :rtype: List[int] """ indexes = [] n ,num = len(s), len(words) if n == 0 or num == 0: return indexes wordLen = len(words[0]) counts = collections.Counter(words) for i in xrange( n - num * wordLen + 1): seen = dict() # seen = defaultdict(int) j = 0 while j < num: word = s[i + j * wordLen : i + (j + 1) * wordLen] if word in counts: seen[word] = seen.get(word, 0) + 1 #seen[word] += 1 if seen[word] > counts[word]: break else: break j += 1 if j == num: indexes.append(i) return indexes;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
解法2：
s = “barfoofoobarthefoobarman”,
words = [“bar”,“foo”,“the”]
首先还是建立map记录words数组出现单词的数量：m1:{ “foo”：1，“bar”：1，“the”：1}
暴力法是每次移动一个字符，而该方法每次移动一个单词
外层循环 i 只需遍历一个单词的长度即可即i < 3
而内层循环则需每次增加一个单词的长度，这样就可以遍历所有情况
第一次遍历：
i ： 0 j 为 0 3 6 9 12 15 18 21
初始化左边界left = i = 0 ，count = 0，为匹配的个数，为了比较方便，另建map m2：记录在窗口中的单词的数量
首先取第一个单词"bar"，m1中有"bar"，m2中"bar"的数量加1：{ “bar”：1}，同时m2中"bar"的数量小于等于m1，匹配的个数加1，变为1
接着取第二个单词"foo"，m1中有"foo"，m2中"foo"的数量加1：{ “bar”：1，“foo”：1}，同时m2中"foo"的数量没有超过m1，匹配的个数加1，变为2
接着取第二个单词"foo"，m1中有"foo"，m2中"foo"的数量加1：{ “bar”：1，“foo”：2}，此时m2中"foo"的数量超过m1，必须左移左边界的值，移去最左边的"bar"，m2：{ “foo”：2}，同时必须判断m2中"bar"的数量小于m1，匹配的个数减1，变为1，left变为3
此时此时m2中"foo"的数量超过m1，必须再次左移，移去最左边的"foo"，m2：{ “foo”：1}，此时m2中"foo"的数量等于m1，匹配的个数不能减1，因为之前"foo"数量增多时，匹配的个数没有增加，left变为6，再次判断m2中"foo"的数量没有超过m1，结束循环
此时left为6，count为1，m2：{ “foo”：1}，j = 9,取单词"bar"，m1中有"bar"，m2中"bar"的数量加1：{ “foo”：1，“bar”：1}，同时m2中"bar"的数量没有超过m1，匹配的个数加1，变为2，
接着取下一个单词"the"，m1中有"the"，m2中"the"的数量加1：{ “foo”：1，“bar”：1，“the”：1}，同时m2中"the"的数量没有超过m1，匹配的个数加1，变为3，此时匹配的数量等于words的个数，说明已经找到一组解，将left = 6放入结果向量即可，
接下来只需舍弃窗口中的最左边的单词即可，移去最左边的"foo",m2 ：{“bar”：1，“the”：1}匹配的个数减1，变为2，同时left变为9
同样的我们得到结果9和12
此时left为15，count为2，m2：{ “foo”：1，“bar”：1}，j = 21,取单词"man"，m1中没有有"man"，说明窗口断了，必须重新开始，left直接移向"man"的后一个单词，left = 24，map清空，count置0，j更新为24，超过21结束第一次循环
第二次遍历：
i ： 1 j 为 1 4 7 10 13 16 19 22
第三次遍历：
i ： 2 j 为 2 5 8 11 14 17 20 23，其余过程同第一次遍历
c++：
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> indexes; int n = s.size(); int num = words.size(); if(n == 0 || num == 0) return indexes; int len = words[0].size(); unordered_map<string, int> m1; for(string s : words){ m1[s]++; } for(int i = 0; i < len; i++){ int left = i; int count = 0; unordered_map<string, int> m2; for(int j = i; j <= n - len; j += len){ string temp = s.substr(j , len); if(m1.count(temp)){ m2[temp]++; if(m2[temp] <= m1[temp]){ count++; } else { while(m2[temp] > m1[temp]){ string temp1 = s.substr(left , len); m2[temp1]--; if(m2[temp1] < m1[temp1]) count--; left += len; } } if(count == num){ indexes.push_back(left); string temp2 = s.substr(left , len); m2[temp2]--; count--; left += len; } } else { m2.clear(); left = j + len; count = 0; } } } return indexes; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
java：
class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> indexes = new ArrayList<>(); int n = s.length(); int num = words.length; if(n == 0 || num == 0 || s == null || words == null) return indexes; int len = words[0].length(); Map<String, Integer> m1 = new HashMap<>(); for(String word : words) { m1.put(word, m1.getOrDefault(word, 0) + 1); } for(int i = 0; i < len; i++){ Map<String, Integer> m2 = new HashMap<>(); int left = i; int count = 0; for(int j = i; j <= n - len; j += len){ String word = s.substring(j, j + len); if(m1.containsKey(word)){ m2.put(word, m2.getOrDefault(word, 0) + 1); if(m2.get(word) <= m1.get(word)){ count++; } else { while(m2.get(word) > m1.get(word)){ String newWord = s.substring(left, left + len); m2.put(newWord , m2.get(newWord) - 1); if(m2.get(newWord) < m1.get(newWord)) count--; left += len; } } if(count == num) { indexes.add(left); String newWord = s.substring(left, left + len); m2.put(newWord , m2.get(newWord) - 1); count--; left += len; } } else { m2.clear(); left = j + len; count = 0; } } } return indexes; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
python:
class Solution(object): def findSubstring(self, s, words): """ :type s: str :type words: List[str] :rtype: List[int] """ indexes = [] n ,num = len(s), len(words) if n == 0 or num == 0: return indexes wordLen = len(words[0]) m1 = collections.Counter(words) for i in xrange(wordLen): left , count , j = i , 0 , i m2 = dict() while j <= n - wordLen: word = s[j : j + wordLen] if word in m1: m2[word] = m2.get(word, 0) + 1 if m2[word] <= m1[word]: count += 1 else: while m2[word] > m1[word]: newWord = s[left : left + wordLen] m2[newWord] = m2.get(newWord) - 1 if m2[newWord] < m1[newWord]: count -= 1 left += wordLen if count == num: indexes.append(left) newWord = s[left : left + wordLen] m2[newWord] = m2.get(newWord) - 1 count -= 1 left += wordLen else: m2.clear() count = 0 left = j + wordLen j += wordLen return indexes
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
