leetcode30

清疚 2022-08-09 03:24 168阅读 0赞

LeetCode30-----------Substring with Concatenation of All Words

看题目都有些费劲，要不是看了几组Custom Testcase才知道题意，顺便说一句Custom Testcase这个功能在调试的时候真的非常实用。

题目意思：

给定一个字串不妨称为母串S，和一组单词，他们保存在一个string的顺序容器Words中，并且满足一个条件，单词长度相等。

现在要找S中所有满足条件A的索引的集合并在int的顺序容器中返回。

这个条件A描述起来还有些复杂：

以该索引index为起点的子串中，包含了Words中的所有单词，当然Words中的单词没有顺序。

例如题目中给的：

s："barfoothefoobarman"

words：\["foo", "bar"\]

标准输出：

\[0,9\]

即，以索引0为起点长度为6的子串"barfoo"包含 “foo” "bar"这两个单词，索引9为起点"foobar"同样包含"foo""bar"这两个单词。

好了，分析一下这道题目的关键是：

1.单词是定长的，示例中为3。

2.需要查询的子串的长度也是固定的，示例中为6（word个数\*word长度）

最后思路就简单了。

两层循环。

大循环表示索引index从0递增。

小循环从起index处取出子串来找是否有单词（这一步通过一个辅助map实现）

这种方法有点像朴素的模式匹配，不知道有没有效率更高的算法，欢迎交流。

一些细节在注释中体现。

代码：

class Solution {
    public:
    	vector<int> findSubstring(string s, vector<string>& words) {
    		vector<int>result;
    		if (s == "" || words.empty())//空
    		{
    			return result;
    		}
    		int sLen = s.size();//母串的总长度
    		int wordLen = words[0].size();//单个单词的长度
    		int wordCount = words.size();//单词的个数
    		int subLen = wordLen * wordCount;//每次需要从母串中拿来进行匹配的子串的长度
    		map<string, int>myWords;
    		int i;
    		int j;
    		int k;
    		for (i = 0; i < wordCount; i++)
    		{
    			myWords[words[i]] = myWords[words[i]] + 1;
    		}//用来记录words中所有word出现的次数用于后面的计算
    		i = 0;
    		int count;
    		while (i < sLen - subLen + 1)
    		{
    			map<string, int>tempMap(myWords);
    			count = 0;
    			int subCount = i + subLen;//临时保存母串中需要拿出来匹配的长度
    			//不能直接while(k<subLen + i)因为满足当i自增后会循环条件变化，内循环会多循环一次
    			k = i;
    			//while (k < subCount + 1)
    			while (k < subCount)
    			{
    				string temp = s.substr(k, wordLen);//取出一个与word长度一样的子串
    				if (tempMap.find(temp) == tempMap.end())//没有找到说明从i开头的子串中没有需要的单词，这个直接时候i++，并跳出循环 
    				{
    					i++;
    					break;
    				}
    				else
    				{
    					if (tempMap[temp] > 0)
    					{
    						tempMap[temp]--;//”用过“的单词从临时Map中剔除
    						k += wordLen;//k跳到下一个单词
    						count++;
    					}
    					//虽然找到，但多余了，也要剔除
    					else
    					{
    						i++;
    						break;
    					}
    				}
    				//关于何时往结果集中添加。我目前的办法是，在子串中每找到一个
    				//单词count++，直到找到所有单词，即count==wordCount
    				//希望有更好的办法
    				if (count == wordCount)
    				{
    					result.push_back(i);
    					tempMap.clear();
    					i++;
    				}
    			}
    		}
    		return result;
    	}
    };