Consider the string s
to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s
will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
Now we have another string p
. Your job is to find out how many unique non-empty substrings of p
are present in s
. In particular, your input is the string p
and you need to output the number of different non-empty substrings of p
in the string s
.
Note: p
consists of only lowercase English letters and the size of p might be over 10000.
Example 1:
Input: "a" Output: 1 Explanation: Only the substring "a" of string "a" is in the string s.
Example 2:
Input: "cac" Output: 2 Explanation: There are two substrings "a", "c" of string "cac" in the string s.
Example 3:
Input: "zab" Output: 6 Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.
A:
首先,就是从每一个start index, 然后往后看,后面的是不是substring of s
class Solution { public: int findSubstringInWraproundString(string p) { int n = p.length(); unordered_set<string> mySet; for(int start =0; start <n; start++){// both start and end are inclusive for(int end = start;end<n;end++){ // both start and end are inclusve if(end == start || p[end] == p[end-1] +1 || ( p[end]=='a' && p[end-1] == 'z') ){ mySet.insert(p.substr(start, end-start+1)); }else{ break; } } } return mySet.size(); } };
然而LTE了
究其原因,如果p 是duplicated. 那么我们有太多重复计算的了。 (而且 len(p) > 10,000. 然而我们的字母只有26个)
很显然, 改进应该是在里面的这个for Loop
考虑这样的p
"zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghifklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...".
这样就会每个都跑到最后去了
因此,我的idea是,对于每一个字母,例如'a', 找出其从他开始最长的串儿。
其长度,就是以 ‘a' 开始的字符串的数目
class Solution { public: int findSubstringInWraproundString(string p) { int n = p.length(); vector<int> maxLen(26,0);// maxLength of maxLen[ch-'a'] that it can reach for(int start =0; start <n; ){ int end = start+1; // keep going untill we find non-fit position for(;end<n;end++){ if( p[end] != p[end-1] +1 && not (p[end]=='a' && p[end-1] == 'z') ){ break; } } for(int i =start;i<min(end, start+26);i++){ int index = int(p[i]) - 'a'; maxLen[index] = max(maxLen[index], end - i); } start = end; } return accumulate(maxLen.begin(), maxLen.end(), 0); } };
No comments:
Post a Comment