aboutsummaryrefslogtreecommitdiff
path: root/palindromic_substrings.cpp
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /palindromic_substrings.cpp
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'palindromic_substrings.cpp')
-rw-r--r--palindromic_substrings.cpp31
1 files changed, 31 insertions, 0 deletions
diff --git a/palindromic_substrings.cpp b/palindromic_substrings.cpp
new file mode 100644
index 0000000..8de80a0
--- /dev/null
+++ b/palindromic_substrings.cpp
@@ -0,0 +1,31 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ int countSubstrings(string s) {
+ this->s = s;
+ int ans = 0, n = s.size();
+ dp.resize(n, vector<int>(n, -1));
+ for (int i = 0; i < n; i++)
+ for (int j = i; j < n; j++)
+ ans += helper(i, j, s);
+ return ans;
+ }
+
+private:
+ vector<vector<int>> dp;
+ // string s = "abc";
+ int helper(int l, int r, string s) {
+ if (l > r || l == r)
+ return 1;
+ if (dp[l][r] != -1)
+ return dp[l][r];
+ if (s[l] != s[r])
+ return dp[l][r] = 0;
+ if (helper(l + 1, r - 1, s))
+ return dp[l][r] = 1;
+ return dp[l][r] = 0;
+ }
+};
+
+int main() {}