首页 > 代码库 > LeetCode: Substring with Concatenation of All Words [029]
LeetCode: Substring with Concatenation of All Words [029]
【题目】
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9]
.
(order does not matter).
【题意】
给定一个字符串S和一个词典L, 从S中找出所有的子串的初始位置,这些子串有L中的所有单词组成,L中的每个单词只使用一次,子串中不包含词典以外的其他单词。注意:词典中所有单词的长度都一样
【思路】
用一个长度为L.length()*word.length()的滑动窗口,返回符合条件的窗口起始地址。窗口合法性的判断用一个辅助的map来实现,map记录一个窗口中该出现的词,以及每个词应该出现的个数【注意:词典中可能出现的重复的词】
【代码】
class Solution { public: vector<int> findSubstring(string S, vector<string> &L) { vector<int> result; int slen=S.length(); //字符串长度 int lsize=L.size(); //词典中的单词数 if(lsize==0)return result; //词典为空 int wordLen=L[0].length(); int window=lsize*wordLen; if(slen<window)return result; //滑动窗口比S长 //初始化辅助map map<string, int> dict; for(int i=0; i<lsize; i++) dict[L[i]]+=1; //搜索 for(int i=0; i<=slen-window; i++){ map<string, int> tempdict; //辅助当前窗口的map int wordStart=i; for(; wordStart<i+window; wordStart+=wordLen){ string word=S.substr(wordStart, wordLen); if(dict[word]==0)break; //如果当前单词没有在字典中出现过,直接break else if(dict[word]==tempdict[word])break; //如果当前单词已经出现过字典中指定的次数,说明当前单词是多出来的,直接break else tempdict[word]+=1; //累计单词出现的次数 } if(wordStart==i+window)result.push_back(i); } return result; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。