467.环绕字符串中唯一的子字符串
467.环绕字符串中唯一的子字符串
题解
题目:给一个a到z的字符串s,并且定义该字符串s是无限环绕的,即a…xyzabcd…yzabc…,给一个字符串p,问p中的有多少个子串,出现在s中。例如p=cab,则 a,b,c,ab这4个子串在s中出现过
思路:动态规划
p=bcd b 1(b) bc 2(c,bc) bcd 3(d,cd,bcd) p=cab c 1(c) ca 1(a) cab 2(b,ab) 在周期字符串s中,如果知道了子串的最后一个字符,以及子串长度,那么该字符串就被确定了 题目要求的是不同子串个数,那么对于相同字符结尾的子串,长的子串必定包含短的子串---bcd abcd 定义dp[i]:在p中以字符串i结尾的子串的 最长长度,知道了最长长度,那么就知道了以i结尾的不同子串的个数了 递推公式:如果p[i]是p[i-1]的下一个字母,则递增k,否则k=1,重新开始计算连续递增的子串长度 dp[p[i]]=max(dp[p[i]],k) 最后再将,以a,b,c..结尾的子串的最长长度相加,就是答案了
代码
func findSubstringInWraproundString(p string) (ans int) { dp := [26]int{} k := 0 for i, v := range p { if i > 0 && (v-int32(p[i-1])+26)%26==1 { k++ } else { k = 1 } dp[v-'a'] = max(dp[v-'a'], k) } for _, v := range dp { ans += v } return ans } func max(a, b int) int { if b > a { return b } return a }