647. Palindromic Substrings

Leetcode 链接

题目

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Note:
The input string length won't exceed 1000.

题意解析

找出字符串中所有的回文串。注意：单个字符也算回文串。

解决方案

• 在每个字符的左右两边加上特殊字符 "#"，从而使得字符串长度变为奇数。例 1)：abba =》 #a#b#b#a# 例 2): aba => #a#b#a#
• 以每一个字符为中心，开始向两边寻找，判断两边的字符是否相等，如果相等则为回文串并且继续向两边扩展，如果不相等则结束此次搜索

Go 代码

func countSubstrings(s string) int {
    str := "#"
    for _, v := range s {
        str += string(v) + "#"
    }

    cnt := 0

    tmp := []rune(str)
    for i:=0; i<len(tmp); i++ {
        from := i-1
        to := i+1

        if tmp[i] != '#'{
            cnt += 1
        }

        for from >= 0 && to < len(tmp) && tmp[from] == tmp[to] {
            if tmp[from] != '#'{
               cnt++
            }

            from--
            to++
        }
    }

    return cnt
}