LeetCode Palindromic Substrings 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.
给定一个字符串，问该字符串中有多少个回文子串。 暴力解法就是枚举每个子串，判断子串是否是回文串。判断一个字符串是否是回文串，可以用首尾指针法，也可以用中心扩展法，方法很多，需要O(n)时间，所以暴力总时间是O(n^3)。 稍微高效一点的方法是，不枚举子串，直接对每个字符用中心扩展法，请看讨论区代码。 我的解法是O(n^2)的DP方法，dp[i][j]表示子串[i,j]是否是回文串。首先对于长度为1的子串dp[i][i]=1肯定都是回文串；求dp[i][j]时，如果s[i]==s[j]且dp[i+1][j-1]是回文串，则dp[i][j]=1也是回文串。 最后统计一下dp数组中有多少个1就有多少个回文子串。 代码如下： [cpp] class Solution { public: int countSubstrings(string s) { int ans = 0, n = s.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = 0; i < n; ++i) { dp[i][i] = 1; ++ans; } for (int len = 2; len <= n; ++len) { for (int i = 0; i < n; ++i) { int j = i + len – 1; if (j >= n)break; if (s[i] == s[j] && (len == 2 || dp[i + 1][j – 1] == 1)) { dp[i][j] = 1; ++ans; } } } return ans; } }; [/cpp] 本代码提交AC，用时12MS。]]>