[leetcode] 467. Unique Substrings in Wraparound String

[leetcode] 467. 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.

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.

分析

题目的意思是：给定一个字符串，求出其不重复非空子字符串的个数。

这里用了一个技巧，例如abcd字符串，以d结尾的子字符串有abcd, bcd,cd,d。bcd,cd,d都包含在abcd中，那么知道某个字符结束的最大字符串包含其他以该字符结束的字符串的字符串都包含在abcd中。题目就可以转换为分别求出以每个字符(a-z)为结束字符的最长连续字符串就行了，用一个数组cnt记录下来，最后在求出数组cnt的所有数字之和即为结果。

代码

class Solution {public: int findSubstringInWraproundString(string p) { vector cnt(26,0); int len=1; for(int i=0;i0&&(p[i]-p[i-1]==1||p[i-1]-p[i]==25)){ len++; }else{ len=1; } cnt[p[i]-'a']=max(cnt[p[i]-'a'],len); } return accumulate(cnt.begin(),cnt.end(),0); }};

参考文献

​​[LeetCode] Unique Substrings in Wraparound String 封装字符串中的独特子字符串​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。