647. 回文子串

題目鏈接
文章講解
回溯法

class Solution {
public:int count = 0;// 檢查字符串是否是回文bool isPalindrome(string& s, int start, int end) {while (start < end) {if (s[start] != s[end]) return false;start++;end--;}return true;}// 回溯法，嘗試從每個位置生成子串void backtrack(string& s, int start) {int n = s.size();for (int end = start; end < n; end++) {if (isPalindrome(s, start, end)) {  // 如果是回文count++;  // 增加回文子串的計數}}}int countSubstrings(string s) {int n = s.size();for (int i = 0; i < n; i++) {backtrack(s, i);  // 從每個字符開始，回溯生成子串}return count;}
};

暴力

class Solution {
public:int count = 0;// 檢查字符串是否是回文bool isPalindrome(string& s, int start, int end) {while (start < end) {if (s[start] != s[end]) return false;start++;end--;}return true;}int countSubstrings(string s) {int n = s.size();for (int i = 0; i < n; i++) {for(int j=i;j<n;j++){if(isPalindrome(s,i,j))count++;}}return count;}
};

dp

class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));int result = 0;for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍歷順序for (int j = i; j < s.size(); j++) {if (s[i] == s[j]) {if (j - i <= 1) { // 情況一 和 情況二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情況三result++;dp[i][j] = true;}}}}return result;}
};

516.最長回文子序列

題目鏈接
文章講解

class Solution {
public:int longestPalindromeSubseq(string s) {int n=s.size();vector<vector<int>> dp(n,vector<int>(n,0));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(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);}}return dp[0][n-1];}
};