leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0131.cpp (1453B)

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