回文子串

1. 题目描述

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

2. 思路

• 暴力
• 中心扩展

3. 实现

3.1. 暴力

• 递归

//递归
func countSubstrings(s string) int {
	count := 0

	countSubstringsDFS(s, 0, &count)

	return count
}

func countSubstringsDFS(s string, length int, count *int) {
	if length > len(s) {
		return
	}

	for i := 0; i < len(s)-length; i++ {
		if isHuiWen(s, i, i+length) {
			*count++
		}
	}

	countSubstringsDFS(s, length+1, count)
}

• 循环

//循环
func countSubstrings2(s string) int {
	count := 0

	for i := 0; i < len(s); i++ {
		for j := 0; j < len(s)-i; j++ {
			if isHuiWen(s, j, j+i) {
				count++
			}
		}
	}

	return count
}

3.2. 中心扩展

func countSubstrings(s string) int {
    chars := []rune(s)
    res := 0
    for i, _ := range chars {
        res += spread(chars, i,i)
        res += spread(chars, i,i+1)
    }
    return res
}

func spread(chars []rune, left ,right int) int {
    count := 0
    for left >= 0 && right <= len(chars)-1 {
        if chars[left] == chars[right] {
            count++
            left--
            right++
        }else {
            break
        }
    }
    return count
}

4. 参考

• 647. 回文子串 - 力扣（LeetCode）