第38天。
今天的题目是Unique Substrings in Wraparound String:
这道题麻烦的地方在于,子串需要去除重复。我们把问题转换一下,即以字符 c 结尾的子串的个数。不难发现,最长长度和子串个数是相同的。这样的话,我们可以在遍历时维护一个变量len
来保存,以当前字符结尾的子串的长度,通过判断当前字符与上一个字符是否在s
中相邻,来确定以当期字符结尾的子串的个数。同时,为了去除重复,我们可以用一个长度为26的字典来保存每个以字符 c 结尾的子串的最长长度。最后,我们只需要对字典进行一次求和即可。
1int findSubstringInWraproundString(string p) {2 if (p.size() == 0) return 0;3
4 vector<int> dict(26, 0);5 int len = 1;6 int prev = p[0] - 'a';7 dict[prev] = 1;8
9 for(int i = 1;i < p.size();i++) {10 int temp = p[i] - 'a';11 if ((prev + 1) % 26 == temp) {12 dict[temp] = max(++len, dict[temp]);13 } else { len = 1; dict[temp] = max(dict[temp], 1); }14 prev = temp;15 }6 collapsed lines
16
17 // sum18 int res = 0;19 for(auto i: dict) res += i;20 return res;21}