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函数,我在实际做题的时候有了新的认识,这点在代码中再说。