leetcode

commit 374d6543f2d12512b4aa73a958bafd1bc5f1d55d
parent 283a31b1e87c9ed6c7445084e0f292a91d80f2bb
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 22 Jan 2023 12:08:19 +0100

Daily Problem

Diffstat:
A
Problems/0131.cpp
 | 
60
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 61 insertions(+), 0 deletions(-)
diff --git a/Problems/0131.cpp b/Problems/0131.cpp
@@ -0,0 +1,60 @@
+// Backtracking
+class Solution {
+  vector<string> st;
+  vector<vector<string>> res;
+
+  bool valid(const string &s) {
+    int i = 0, j = s.size() - 1;
+    while (i < j)
+      if (s[i++] != s[j--]) return false;
+    return true;
+  }
+
+  void dfs(const string &s, int pos) {
+    if (pos == s.size()) res.push_back(st);
+
+    string crnt = "";
+    for (int i = pos; i < s.size(); i++) {
+      crnt += s[i];
+      if (valid(crnt)) {
+        st.push_back(crnt);
+        dfs(s, i + 1);
+        st.pop_back();
+      }
+    }
+  }
+
+public:
+  vector<vector<string>> partition(string s) {
+    dfs(s, 0);
+    return res;
+  }
+};
+
+// Backtracking with DP
+class Solution {
+  vector<string> st;
+  vector<vector<string>> res;
+
+  void dfs(const string &s, int pos, vector<vector<bool>> &dp) {
+    if (pos == s.size()) res.push_back(st);
+
+    string crnt = "";
+    for (int i = pos; i < s.size(); i++) {
+      crnt += s[i];
+      if (s[pos] == s[i] && (i - pos < 2 || dp[pos + 1][i - 1])) {
+        dp[pos][i] = true;
+        st.push_back(crnt);
+        dfs(s, i + 1, dp);
+        st.pop_back();
+      }
+    }
+  }
+
+public:
+  vector<vector<string>> partition(string s) {
+    vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
+    dfs(s, 0, dp);
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -79,6 +79,7 @@ for solving problems.
 |  0124  |    Hard    | [Binary Tree Maximum Path Sum](Problems/0124.cpp)                                                |
 |  0125  |    Easy    | [Valid Palindrome](Problems/0125.cpp)                                                            |
 |  0129  |   Medium   | [Sum Root to Leaf Numbers](Problems/0129.cpp)                                                    |
+|  0131  |   Medium   | [Palindrome Partitioning](Problems/0131.cpp)                                                     |
 |  0133  |   Medium   | [Clone Graph](Problems/0133.cpp)                                                                 |
 |  0134  |   Medium   | [Gas Station](Problems/0134.cpp)                                                                 |
 |  0135  |    Hard    | [Candy](Problems/0135.cpp)                                                                       |