给定一个长度为 n 的字符串,请你统计并返回这个字符串中回文子串的数目。
回文子串:字符串中连续字符组成的一个子串,这个子串正着读和倒着读一样。
只要开始位置和结束位置不同,相同字符组成的子串也视为不同的回文子串。
数据范围:字符串的长度满足 ,字符串中仅出现小写英文字母
"nowcoder"
8
"nnn"
6
六个回文子字符串分别是 n , n , n , nn , nn , nnn
package main //import "fmt" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str string字符串 * @return int整型 */ func Substrings( str string ) int { ans:=0 for i:=0;i<len(str);i++{ for j:=i+1;j<=len(str);j++{ if check(str[i:j]){ ans++ } } } return ans } func check(s string)bool{ i,j:=0,len(s)-1 for i<j{ if s[i]!=s[j]{ return false } i++ j-- } return true }
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param str string字符串 # @return int整型 # class Solution: """ 题目: https://www.nowcoder.com/practice/3e8b48c812864b0eabba0b8b25867738?tpId=196&tqId=40443&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title= 算法: 设dp[i][j]表示字符串str的子串str[i: j+1]是否为回文串,本题要求计算有多个回文子串,也就是统计dp[i][j] = True的数量 状态转移方程: 若i = j: dp[i][j] = True 若str[i] = str[j]: 若i + 1 = j: dp[i][j] = True 否则: dp[i][j] = dp[i + 1][j - 1] 复杂度: 时间复杂度:O(n^2), n为字符串str的长度 空间复杂度:O(n^2) """ def Substrings(self, str): # write code here n = len(str) dp = [[False] * n for _ in range(n)] res = 0 for i in range(n - 1, -1, -1): for j in range(i, n): if i == j: dp[i][j] = True elif str[i] == str[j]: if i + 1 == j: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] if dp[i][j] == True: res += 1 return res if __name__ == "__main__": sol = Solution() # str = "nowcoder" str = "nnn" res = sol.Substrings(str) print res
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str string字符串 * @return int整型 */ int Substrings(string str) { int n = str.size(); int res=n; if(n<2) return n; vector<vector<int>>dp(n,vector<int>(n)); //base case for(int i=0;i<n;i++){ dp[i][i]=1; } for(int i=n-1;i>=0;i--){ for(int j=i+1;j<n;j++){ if(str[i]==str[j]){ if(j-i<3){ dp[i][j]=1; res++; }else{ if(dp[i+1][j-1]){ dp[i][j]=1; res++; } } } } } return res; } };