首页 > 代码库 > 467. Unique Substrings in Wraparound String
467. Unique Substrings in Wraparound String
https://leetcode.com/problems/unique-substrings-in-wraparound-string/#/description
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.
dp.
用一个length数组记录每个字母作为最大子串的最后一个字母时的子串长度。
1 class Solution { 2 public: 3 int findSubstringInWraproundString(string p) { 4 vector<int> length(26,0); 5 const int size=p.length(); 6 int len=0,num=0; 7 for(int i=0;i<size;i++) 8 { 9 int cur=p[i]-‘a‘; 10 //比较现在的字母和前一个字母,(x+25)%26可以得到前一个字母(a为0...z为26) 11 if(i!=0&&p[i-1]!=(cur+25)%26+‘a‘) 12 len=0; 13 if(++len>length[cur])//++表示每个字母至少为长度为1的子串的最后一个字母 14 { 15 num+=len-length[cur];//由于s串固定,所以子串从最后一个字母往前推都是固定的,只是可以推多长不确定 16 length[cur]=len;//当前字母作为最后一个字母的子串还可以增长 17 } 18 } 19 return num; 20 } 21 };
467. Unique Substrings in Wraparound String
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。