467. 环绕字符串中唯一的子字符串
https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
难度中等348
把字符串 s 看作 "abcdefghijklmnopqrstuvwxyz" 的无限环绕字符串，所以 s 看起来是这样的：
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."。
现在给定另一个字符串 p 。返回 s 中 不同 的 p 的 非空子串 的数量 。
示例 1：
输入：p = "a" 输出：1 解释：字符串 s 中只有 p 的一个 "a" 子字符。
示例 2：
输入：p = "cac"
输出：2
解释：字符串 s 中只有 p 的两个子串 ("a", "c") 。
示例 3：
输入：p = "zab"
输出：6
解释：在字符串 s 中有 p 的六个子串 ("z", "a", "b", "za", "ab", "zab") 。
提示：
1 <= p.length <= 105p由小写英文字母组成
通过次数33,517提交次数64,765
class Solution {
public int findSubstringInWraproundString(String p) {
int [] dp = new int[26];
int n =0;
for(int i=0;i<p.length();i++)
{
if(i>0 && (p.charAt(i-1)+1==p.charAt(i)||p.charAt(i-1)=='z'&&p.charAt(i)=='a')||p.charAt(p.length()-1)=='z'&&p.charAt(0)=='a')
{
++n;
}
else n=1;
dp[p.charAt(i)-'a'] = Math.max(dp[p.charAt(i)-'a'],n);
}
int ans = 0;
for(int i=0;i<26;i++) ans+=dp[i];
return ans;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/68985.html
