leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0131.cpp (1453B)

      1 // Backtracking
      2 class Solution {
      3     vector<string> st;
      4     vector<vector<string>> res;
      5 
      6     bool valid(const string &s) {
      7         int i = 0, j = s.size() - 1;
      8         while (i < j)
      9             if (s[i++] != s[j--]) return false;
     10         return true;
     11     }
     12 
     13     void dfs(const string &s, int pos) {
     14         if (pos == s.size()) res.push_back(st);
     15 
     16         string crnt = "";
     17         for (int i = pos; i < s.size(); i++) {
     18             crnt += s[i];
     19             if (valid(crnt)) {
     20                 st.push_back(crnt);
     21                 dfs(s, i + 1);
     22                 st.pop_back();
     23             }
     24         }
     25     }
     26 
     27   public:
     28     vector<vector<string>> partition(string s) {
     29         dfs(s, 0);
     30         return res;
     31     }
     32 };
     33 
     34 // Backtracking with DP
     35 class Solution {
     36     vector<string> st;
     37     vector<vector<string>> res;
     38 
     39     void dfs(const string &s, int pos, vector<vector<bool>> &dp) {
     40         if (pos == s.size()) res.push_back(st);
     41 
     42         string crnt = "";
     43         for (int i = pos; i < s.size(); i++) {
     44             crnt += s[i];
     45             if (s[pos] == s[i] && (i - pos < 2 || dp[pos + 1][i - 1])) {
     46                 dp[pos][i] = true;
     47                 st.push_back(crnt);
     48                 dfs(s, i + 1, dp);
     49                 st.pop_back();
     50             }
     51         }
     52     }
     53 
     54   public:
     55     vector<vector<string>> partition(string s) {
     56         vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
     57         dfs(s, 0, dp);
     58         return res;
     59     }
     60 };