网站建设的报告,北京注册公司地址有什么要求,网站选域名,wordpress 安装失败寻找回文子串的完整思路过程前言一、回文串的数量二、动态规划1、完整思考过程2、go总结参考文献前言
回文字符串#xff0c;就是从左遍历和从右遍历的字符是相同顺序的#xff0c;转换一下#xff0c;就是该字符串是对称的。寻找回文子串面临两个直接的问题#xff0c;1-…
寻找回文子串的完整思路过程前言一、回文串的数量二、动态规划1、完整思考过程2、go总结参考文献前言
回文字符串就是从左遍历和从右遍历的字符是相同顺序的转换一下就是该字符串是对称的。寻找回文子串面临两个直接的问题1-如何确定一个子串2-如何判断该子串是否为回文串
一、回文串的数量 二、动态规划
1、完整思考过程
两个直观的问题 1如何确定子串两层for循环O(n2)定位左右边界。 2如何判定子串是回文子串for循环O(n)判定是否对称。 复杂度O(n3)
子串/子数组问题联想前缀/滑动窗口/单调栈/动态规划 回文内在特点一个回文串本身有什么特点去头去尾也是回文利用这个规律记录内串是否为回文从内到外递进判断可以减少for循环的对称判断则可将时间复杂度降为O(n2)
方案由内到外从少到多先判断s[:0]子串再判断s[:1]子串依次类推。
2、go
func countSubstrings(s string) int {f : make([]bool,len(s))cnt : 0for i : 0;i len(s);i {f[i] truecnt // 每个字符串都是一个回文这里cnt配合f[i] ture相互理解而不是cnt : len(s)// 需要用到f[j1],所以正序遍历防止覆盖。for j : 0;j i;j {f[j] false // 复用一层数组需要覆盖前面的值保持严格递推。if s[i] s[j] (j 1 i || f[j 1]) {f[j] truecnt}}}return cnt
}总结
1写下完整的思路过程有助于清晰的理解问题记忆问题的解答思路。 2动态规划本质将问题分解成规模不同性质相同的子问题找到子问题之间的内在联系此时便可记录这种联系点以空间换时间。 3动态规划常常涉及空间压缩而压缩面临直观的两个问题1-这个记录的状态是否过时2-这个记录的状态是否太新才覆盖了
参考文献
[1] LeetCode 回文串的数量
