回文子串的数量[寻找回文子串的完整思路过程]-Toy模板网

这篇具有很好参考价值的文章主要介绍了回文子串的数量[寻找回文子串的完整思路过程]。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

回文字符串，就是从左遍历和从右遍历的字符是相同顺序的，转换一下，就是该字符串是对称的。寻找回文子串面临两个直接的问题，1-如何确定一个子串？2-如何判断该子串是否为回文串？

一、回文串的数量

寻找回文子串,数据机构与算法,回文,回文子串,动态规划,状态压缩,go

二、动态规划

1、完整思考过程

两个直观的问题，
1）如何确定子串？两层for循环O(n²)定位左右边界。
2）如何判定子串是回文子串？for循环O(n)判定是否对称。
复杂度：O(n³)

子串/子数组问题，联想前缀/滑动窗口/单调栈/动态规划，
回文内在特点）一个回文串本身有什么特点？去头去尾也是回文，利用这个规律，记录内串是否为回文，从内到外递进判断，可以减少for循环的对称判断，则可将时间复杂度降为O(n²)

方案）由内到外，从少到多，先判断s[:0]子串，再判断s[:1]子串，依次类推。

2、go

func countSubstrings(s string) int {
    f := make([]bool,len(s))

    cnt := 0
    for i := 0;i < len(s);i++ {
        f[i] = true
        cnt++ // 每个字符串都是一个回文，这里cnt++配合f[i] = ture，相互理解，而不是cnt := len(s)
        // 需要用到f[j+1],所以正序遍历，防止覆盖。
        for j := 0;j < i;j++ {
            f[j] = false // 复用一层数组，需要覆盖前面的值，保持严格递推。
            if s[i] == s[j] && (j + 1 == i || f[j + 1]) {
                f[j] = true
                cnt++
            }
        }
    }
    return cnt
}

总结

1）写下完整的思路过程，有助于清晰的理解问题，记忆问题的解答思路。
2）动态规划本质，将问题分解成规模不同性质相同的子问题，找到子问题之间的内在联系，此时便可记录这种联系点，以空间换时间。
3）动态规划常常涉及空间压缩，而压缩面临直观的两个问题，1-这个记录的状态是否过时？2-这个记录的状态是否太新？（才覆盖了）