647. 回文子串

647. 回文子串

暴力

func countSubstrings(s string) int {
    var res int
    for i := 0; i < len(s); i++ {
        for j := i + 1; j <= len(s); j++ {
            if isPalindrome(s[i:j]) {
                res++
            }
        }
    }
    return res
}
func isPalindrome(s string) bool {
    l := 0
    r := len(s) - 1
    for l < r {
        if s[l] != s[r] {
            return false
        }
        l++
        r--
    }
    return true
}

动态规划

func countSubstrings(s string) int {
    var res int
    flag := make([][]bool,len(s))
    for i:=range flag{
        flag[i]=  make([]bool,len(s))
    }
    for j := 0; j < len(s); j++ {
        for i := j ; i >=0; i-- {
            if s[i] == s[j] && (j - i < 2 || flag[i + 1][j - 1]) {
                flag[i][j] = true
                res++
            }
        }
    }
    return res
}

abba
a
b
ba
b
bb
bba
a
ba
bba
abba

func countSubstrings(s string) int {
    if len(s) <= 1 {
        return len(s)
    }
    sLen := len(s)
    palindrome := make([][]bool, sLen)
    for i := 0; i < len(palindrome); i++ {
        palindrome[i] = make([]bool, sLen)
    }
    count := sLen
    for i := sLen - 1; i >= 0; i-- {
        palindrome[i][i] = true
        for j := i + 1; j < sLen; j++ {
            if s[i] == s[j] {
                if j == i+1 {
                    palindrome[i][j] = true
                } else {
                    palindrome[i][j] = palindrome[i+1][j-1]
                }
            }
            if palindrome[i][j] {
                count++
            }
        }
    }
    return count
}
。