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.
For example, given:
s:
"barfoothefoobarman"words:
["foo", "bar"]
You should return the indices:
[0,9].本题是找一个长string里面所有由给定words组成的子串的index。这题跟 “find all anagram of a short string in a long string”的题目意思和解法都是类似的，这种题目是string 里面典型的sliding window的题目，sliding window 能将N^2的题目线性化，将时间复杂度降为O（N）.
所谓的sliding window算法，是说要求处理的字符串是一个给定长度的string，比如这个题目里面要处理的字符串是words.size() * words[0].size()的字符串，那么窗口的长度就是这个值。初始时，窗口为0，由窗口的右边来匹配字符串，CASE 1： 如果匹配，那么继续移动窗口右边words[0].size()个字符，进行下一次匹配，此时窗口越来越大，当完成第一次完全匹配的时候，窗口到达了指定的size，窗口右边继续匹配，此时窗口的左边也要移动，以保证进行匹配的子串是指定的size，宏观上来说，是将整个窗口进行了移动，窗口左边移出的words要补进来，窗口右边移进的words如果匹配要移出去， 整个窗口移动，移动过程中进行这样的匹配，直到窗口右边到达了长string的最右端，表示一次窗口移动匹配完成。 在移动窗口过程中，CASE 2：如果在窗口内窗口右边只要出现一次不匹配，那么所有变量清零，窗口左边移至下一个待匹配的字符串，窗口右边移至窗口左边，再重新进行下一次匹配。sliding window进行字符匹配的时间复杂度是O（N/L）,时间是线性的。
但是本题在base sliding window的基础上加了一点难度，不再只是一次sliding window的匹配，因为窗口左边移动一次要移动1个word的距离，会跳过很多种的情况，（如果是字符匹配，移动窗口是一个字符的距离，一次sliding window就可以了）所以需要对跳过的情况一一进行处理，窗口左边在0-words[0].size的位置，都需要进行sliding window。所以这题的时间复杂度是O（N/L * L)=> O(N) 。
其实这个时间复杂度并不是O（N）， 因为在这其中有两次map copy的操作，其实时间复杂度是O（N*M）, 这种方法在leetcode运行的时间是很长的，也就是效率很低， 下面更新了一个新的算法。
因为words可能有重复，需要用map来存储。
update:
这种固定窗口大小移动的题目，一定要考虑到窗口大小移到固定大小这个case，因为此时就需要移动left， 并且可能要修改map里面的counter 和match 的值，即 right - left >= Window.size的时候，要对窗口左侧进行处理。 此时不管有没有match完全，可能窗口里面的含有不match的word.
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> rst;
//sanity check
if (s.size() < words[0].size() || (s.size() == 0) || (words.size() == 0)) return rst;
//sling window
//store words in a map
map<string, int> wmap;
for (int i = 0; i < words.size(); i++) {
wmap[words[i]]++;
}
map<string, int> bmap = wmap;
//sliding window variable
int slow = 0;//left
int fast = 0; // right
int match = 0; //match counter
for (int i = 0; i < words[0].size(); i++) {
match = 0;
bmap = wmap;
slow = i;
for (fast = slow; fast < s.size(); fast += words[0].size()) {
string tmp = s.substr(fast, words[0].size());
//check if fast match
if (bmap.find(tmp) != bmap.end()) {
bmap[tmp]--;
if (bmap[tmp] == 0) match++;
} else { //not match, move left and all to initial
match = 0;
slow = fast + words[0].size();
bmap = wmap;
continue;
}
//if all match sliding window
if (fast - slow >= words.size() * words[0].size()) {
//move slow, give up slow match
tmp = s.substr(slow, words[0].size());
bmap[tmp]++;
if (bmap[tmp] == 1) match--;
slow += words[0].size();
}
//find a whole match
if (match == wmap.size()) {
rst.push_back(slow);
}
}
}
return rst;
}
};
updated:
将整个string 分成 N - num*len个 num*len的小段，分别对每一个小段进行处理，看这个小段是不是完全匹配，如果能够完全匹配，那么就讲start 的index 存进去， 这种思路跟strStr的思路是很像的，时间复杂度: O((N- len*num)*(num))
总体来说这个算法的时间更少，省去了一些map 复制的操作，也没有太多的substr的操作， 时间上比上面那个好， 但是其实基本的思想差不多，也都是一个固定长度的window在string s上面移动。
对下面这个方法的正确理解是： 对string上面的每一个start position, 都进行words匹配，如果以这个start为起始的words[0].size() * words.size()的string可以匹配，那么就找到了一个匹配的，如果以这个start position 匹配的不成功, start position往前移一位，进行下一次的匹配。 这个思想跟sliding window不同，更加简单一些。 感觉有点小暴力的意思。
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> rst;
if (s.size() < words.size() * words[0].size()) return rst;
int start = 0;
int num = words.size();
int len = words[0].size();
unordered_map<string , int> smap;
for (string st : words) {
smap[st]++;
}
unordered_map<string, int> buf = smap;
for (; start + len * num <= s.size(); start++) {
smap = buf;
int j = 0;//the number of words to match
for (; j < num; j++) {
string tmp = s.substr(start + j*len, len);
if (smap.find(tmp) != smap.end()) {
smap[tmp]--;
if (smap[tmp] < 0) break;
} else {
break;
}
}
if (j == num) rst.push_back(start);
}
return rst;
}
};
leetcode中还有一题sliding window做的题目：
Leetcode 76: Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).For example,
S =
"ADOBECODEBANC"T =
"ABC"Minimum window is
"BANC".
Note:
If there is no such window in S that covers all characters in T, return the emtpy string
"".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
本题是找长字符串中能包含短字符串中字符的最小substring。 也是利用sliding window的思想，分析后发现，本题和上面那题的区别在于，一般的sliding window中的窗口大小是固定的，窗口内是待匹配字符串，窗口右边用于匹配字符，左边移动控制窗口大小，但是这题中的窗口大小显然是变化的，而且窗口内可以有不匹配的子串，但是也是右边用于匹配字符，左边移动控制窗口最小化。
这题的算法是，移动窗口右边，使其达到第一次完全匹配，并且记录此时的substring 长度，因为一次匹配窗口中可能会存在很多不匹配字符，所以通过窗口左边移动来去除不匹配字符，达到缩小窗口的作用。 当达到一次完全匹配的时候，固定窗口右侧，此时右侧一定是一个匹配字符，然后移动左侧，如果移出的字符为一个匹配字符，修改map中的counter，直至match数目变化，以至于窗口内的字符串不够形成一次匹配为止。此时再移动窗口右边，进行下一次完全匹配。 在每次完全匹配的时候需要更新最小窗口长度。
时间复杂度： O（n)
class Solution {
public:
string minWindow(string s, string t) {
//sanity checki
if (s.size() < t.size() || s.size() == 0 || t.size() == 0) return "";
//store t in map
map<char, int> tmap;
for (int i = 0; i < t.size(); i++) {
tmap[t[i]]++;
}
int slow = 0;
int fast = 0;
int match = 0;
int begin = 0;
int end = 0;
int minr = s.size()+1;
bool flag = false; // move slow
for (;fast < s.size(); fast++) {
char c = s[fast];
flag = false;
if (tmap.find(c) != tmap.end()) {
tmap[c]--;
if (tmap[c] == 0) match++;
}
while (match == tmap.size()) { //get one whole match
if (minr > fast - slow+1) {
begin = slow;
end = fast;
minr = fast - slow + 1;
}
if ( tmap.find(s[slow]) != tmap.end() ) {
tmap[s[slow]]++;
if (tmap[s[slow]] == 1) match--;
}
slow++;
}
}
if (minr > s.size()) return "";
return s.substr(begin, minr);
}
};
sliding window题目两类： 1. window 大小固定，找所有匹配； 2. window大小可变，找最小窗口。
No comments:
Post a Comment