Leetcode 30 Substring with Concatenation of All Words 无序map的应用细节
Leetcode 30 Substring with Concatenation of All Words 无序map的应用细节
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].
(order does not matter).
这题意外的收获还是挺大的！恶魔总在细碎处。
题意就是在给定串S中，找出包含且只包含给定字典中所有词的子串的起始位置，并且任意两个词中间不能有交叉字母。
先说说unordered_map。在做这题之前我是不知道这个数据结构的，我只会用map，这题学到了。
两者的接口等基本一致，写代码会map的话，应该也会unordered_map。
map的实现是红黑树，因而修改，查询等操作复杂度是log级别的，同时它的元素也是有序的；
而unordered_map的实现是散列表，基本操作的复杂度是常数级别的，同时元素是无序的；
显然在不关心元素顺序的情况下，后者是通常是更好的选择。
值得一提的是，关于map的find函数，我在实际做题的时候有了新的认识，这点在代码中再说。
再说说思路。
两层循环，第一层列举起始位置0~len-1，第二层以len为步长向后便利，对于遍历到的词分三种情况：
1.在map中，且总共出现的次数未达到字典中的次数；
把这个词加入字符串，继续向后扫描，判断词数是否等于字典大小，等于则求得其中一个结果。
2.在map中，但总共出现的次数已经达到字典中的次数；
从头开始，去掉这个词第一次出现位置之前的所有词，把这个词加入字符串，继续向后扫描。
3.未在map中。
去掉前面所有的词，直接从下一个词开始。
关于时间复杂度，有很多人觉得是word[0].length()*S.length()，其实不然，
第一层循环的复杂度确实为word[0].length()，然而由于第二层的步长为word[0].length()，
所以实际的复杂度依然为S.length()，也就是说是线性的。
<span style="color:#333333;">class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> mp;
vector<int> result;
unordered_map<string, int>::iterator it;
int len=words[0].length(),num=words.size();
for(int i=0;i<len;i++) //起点
{
for(int i=0;i<num;i++)
mp[words[i]]++;
int st=i,cnt=0;
for(int j=i;j<s.length();j+=len)
{
string now=s.substr(j,len);
if(mp.find(now)!=mp.end()) //这里两个判断语句的逻辑顺序进行了调整，不相信可以试试先mp[now]>0,后find(now)时的结果
{
if(mp[now]>0) //这里访问了mp[now],所以即使now不存在，在经过这次访问后程序也自动为它分配了空间
{ //如果find在这之后调用，虽然逻辑上now不存在，但是内存中已然存在，得到的find结果会和想象中不同
mp[now]--;
if(++cnt==num)
{
result.push_back(st);
mp[s.substr(st,len)]++;
st+=len;
cnt--;
}
}
else
{
for(int k=st;k<j;k+=len)
{
if(s.substr(k,len)==now)
{
st=k+len;
break;
}
else
{
mp[s.substr(k,len)]++;
cnt--;
}
}
}
}
else
{
for(int k=st;k<j;k+=len)
mp[s.substr(k,len)]++;
st=j+len;
cnt=0;
}
}
mp.clear();
}
return result;
}
};</span>先说说unordered_map。在做这题之前我是不知道这个数据结构的，我只会用map，这题学到了。
两者的接口等基本一致，写代码会map的话，应该也会unordered_map。
map的实现是红黑树，因而修改，查询等操作复杂度是log级别的，同时它的元素也是有序的；
而unordered_map的实现是散列表，基本操作的复杂度是常数级别的，同时元素是无序的；
显然在不关心元素顺序的情况下，后者是通常是更好的选择。
值得一提的是，关于map的find函数，我在实际做题的时候有了新的认识，这点在代码中再说。