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).
此题我已欲仙欲死……
首先，关于题意的理解，必须所有字典里的串都出现。
其次，暴力法我的代码有问题，超时……关键是我不知道为什么超时，和别人的代码没差多少啊……
痛苦了1个小时之后，我把网上让其他人的代码贴上去，这次没超时，1700ms……
但是，我认为那个代码是不美的，于是我又优化了一下,1600ms,心里那个爽~~~
看了下discuss，有个更优的算法，贴过去，偶滴神啊，190ms……
不过他的算法貌似没用到我的优化方法，理论上这个算法还有优化空间。优化是针对多次出现的重复字段进行的。
呈上暴力法优化后程序。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65 |
class
Solution {public: vector<int> findSubstring(string S, vector<string> &L) { vector<int> re; vector<int> stop(S.length(),0); map<string,int> m; int
l_size = L.size(); int
s_length =S.length(); if(L.size() ==0) return
re; int
size = L[0].length(); for(int
i = 0 ;i < L.size();i++) { m[L[i]]++; } int
ttt =size*l_size; map<string,int> test; for(int
i = 0 ; i + ttt <= s_length;i++ ) { if(stop[i] == 1)continue; test.clear(); int
j; for( j = 0 ; j < l_size ;j++) { string temp = S.substr(i + j*size, size); if(m.find(temp) != m.end()) { test[temp]++; if(m[temp] < test[temp])break; } else { for(int
k = 1 ; k<=j ;k++)stop[i + k*size] = 1; break; } } if(j == l_size) { re.push_back(i); for(int
k = 0 ;i + k*size +size<=s_length ;k++) { string temp1 = S.substr(i + k*size,size); string temp2 = S.substr(i+ttt +k*size,size); if(temp1 == temp2) { stop[i + k*size +size] = 1; re.push_back(i + k*size +size); } else { stop[i + k*size +size] = 1; break; } } } } return
re; }}; |
这题刷的很不爽，还是要笑看人生啊！
这里把比较好的算法贴上来。下次刷的时候把这个算法再优化下。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70 |
class
Solution {private:vector<int> res;map<string,int> cntL;map<string,int> cn;int n ;public:vector<int> findSubstring(string S, vector<string> &L) { res.clear(); cntL.clear(); cn.clear(); n = S.length(); int
e = L.size(); int
t = L[0].length(); int
k = 0; for(int
i = 0; i < e ; i++) { if(cn.count(L[i]) == 0) { cn[L[i]] = 1; k++; } else { cn[L[i]] += 1; k++; } } string tr ,du; int
r = 0; int
st = 0; for(int
j = 0 ; j < t ; j++) { r = 0; st = j; for(int
i = j; i < n; i += t) { tr = S.substr(i,t); if( cn.count(tr) == 0 || cn[tr] == 0 ) { cntL.clear(); r = 0; st = i+t; } else
if(cntL[tr] < cn[tr]) { cntL[tr] += 1; r++; } else { du = S.substr(st,t); while(du != tr) { cntL[du]--; r--; st += t; du = S.substr(st,t); } st += t; } if(r == k) { res.push_back(st); du = S.substr(st,t); cntL[du]--; r--; st += t; } } cntL.clear(); } sort(res.begin(),res.end()); return
res ; }}; |
看了这个算法，洒家这一下午值了！
Substring with Concatenation of All Words,布布扣,bubuko.com
Substring with Concatenation of All Words
原文：http://www.cnblogs.com/pengyu2003/p/3592529.html