注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex30 Substring with Concatenation of All Words  

2015-05-29 23:01:14|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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 wordsexactly 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).


这一题感觉特别冤枉,我是想的太复杂了,用的方法是不断用words里面的单词扫描母串,别人用的是扫描母串,匹配字典。下面是我的没有通过大集合的代码

/*
* 给定一个母字符串,一个words的vector,里面的单词的长度都是一样的
* 搜索一下他们排列后连续出现在s母串中的位置
* 我觉得我这题错的很冤枉 你大爷的,居然是暴力搜索 !!!!!!
*/
class Solution {
public:
vector<int>result;
vector<int> findSubstring(string s, vector<string>& words) {
//words = remvoveRepeat(words);
traverse(s,words);
return result;
}
vector<string>remvoveRepeat(vector<string> words)
{
set<string> mySet;
vector<string> newWords;
for (int i = 0; i < words.size(); i++)
mySet.insert(words[i]);
for (auto &word : mySet)
newWords.push_back(word);
int num;

for (int i = 0; i < newWords.size(); i++)
{
string tmp = newWords[i];
newWords[i].clear();
for (int j = 0; j < words.size(); j++)
{
if (tmp == words[j])
newWords[i].append(words[j]);
}
}
return newWords;
}
bool in(vector<int>index, int location)
{
for (int i = 0; i < index.size(); i++)
{
if (location == index[i])
return true;
}
return false;
}
void traverse(string s, vector<string>& words)
{
/*
* 这个函数用于在s中不断查找words中元素
* 在大的测试集上超时,过不去,这种方法理论上来说确实是有bug的
*/
int len = words.size();
int wordLen = words[0].size();
bool mark = false;
int breakPoint = 0;
vector<int> index;
int i = 0;
int start = 0;
while (true)
{
index.clear();
mark = false;
//字典搜索一遍
for (i = 0; i < len; i++)
{
int location = s.find(words[i], start);
int tmpStart = location;
while (in(index,location))
{
tmpStart = location + wordLen;
location = s.find(words[i], tmpStart);
if (location == string::npos)
{
break;
}
}
if ( location!= string::npos)
{
index.push_back(location);
}
else
{
break;
}
}

if (index.size() == len)
{
sort(index.begin(), index.end());
//排序后查看找到的下标
//我真佩服我自己,这么复杂的逻辑我居然都搞了出来
for (i = 1; i < len; i++)
{
if ((index[i] - index[i - 1]) != wordLen)
{
mark = true;
breakPoint = i;
break;
}
}
if (mark)
{
//找到的不对
start = index[breakPoint-1]+wordLen;
}
else
{
start = index[len-1] +wordLen;
result.push_back(index[0]);
}
}
else
{
break; //while 的退出条件
}

}

//函数结束
}
};

别人就是用的普通的扫描母串的方法~~~呵呵了~~

class Solution {
public:
vector<int>result;
vector<int> findSubstring1(string S, vector<string> &L) {
// Note: The Solution object is instantiated only once.
map<string, int> words;
map<string, int> cur;
int wordNum = L.size();
for (int i = 0; i < wordNum; i++)
words[L[i]]++;
int wordLen = L[0].size();
vector<int> res;
//if(S.size() < wordLen*wordNum)return res;
for (int i = 0; i <= (int)S.size() - wordLen*wordNum; i++)
{
cur.clear();
int j;
for (j = 0; j < wordNum; j++)
{
string word = S.substr(i + j*wordLen, wordLen);
if (words.find(word) == words.end())
break;
cur[word]++;
if (cur[word]>words[word])
break; //因为是切割母串上的字符,可能在dict里面出现的次数大于字典中重复的次数了
}
if (j == wordNum)
res.push_back(i);
}
return res;
}

};

参考
http://blog.csdn.net/doc_sgl/article/details/13022131
http://blog.csdn.net/sunbaigui/article/details/8981321
  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018