Backtrack and bit manipulation

  • backtrack
  • bit manipulation

Backtrack

class Solution {
public:
void backtrack(string& s,int i, vector<string>& current,vector<vector<string>>& ret){
const int n = s.size();
// touch the bottom of the backtracking
if (i == n){
if (is_palindrome(current.back())){
ret.push_back(current);
}
return;
}
// put a separate at position i
if (is_palindrome(current.back())){
current.push_back(s.substr(i, 1));
backtrack(s, i + 1, current, ret);
if (current.back().size() > 1){
current.back().pop_back();
} else {
current.pop_back();
}
}
// do not put a separate at position i
current.back().push_back(s[i]);
backtrack(s, i + 1, current, ret);
if (current.back().size() > 1){
current.back().pop_back();
} else {
current.pop_back();
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> ret;
vector<string> current;
current.push_back(s.substr(0, 1));
if (s.size() == 0) return ret;
if (s.size() == 1) {
ret.push_back({s});
return ret;
}
int i = 1;
backtrack(s, i, current, ret);
return ret;
}
private:
bool is_palindrome(string& c){
const int n = c.size();
if (n <= 1)return true;
int i = 0, j = n - 1;
while (i < j){
if (c[i++] != c[j--])return false;
}
return true;
}
};

Bit Manipulation

class Solution {
public:

vector<vector<string>> partition(string s) {
vector<vector<string>> ret;
const int n = s.size() - 1;
for (int i = 0; i < (1 << n); ++i){
vector<string> candidate = _partition(s, i);
if(are_palindromes(candidate)){
ret.push_back(candidate);
}
}
return ret;

}
private:
bool is_palindrome(string& c){
const int n = c.size();
if (n <= 1)return true;
int i = 0, j = n - 1;
while (i < j){
if (c[i++] != c[j--])return false;
}
return true;
}
bool are_palindromes(vector<string>&candidate){
if (candidate.empty())return true;
for (auto & c: candidate){
if (!is_palindrome(c))return false;
}
return true;
}
vector<string> _partition(string s,int mask){
const int n = s.size();
vector<string> ret;
string curr = "";
for (int i = 0; i < n; ++i){
curr += s[i];
if ((1 << i) & mask){
ret.push_back(curr);
curr = "";
}
}
ret.push_back(curr);
return ret;
}
};

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Recoil State Management in Nextjs

What’s Fragment in ReactJs

DS with JS — Linked Lists — II

Draft-js building search and replace functionality

Project experience with React.js, node.js with koa.js

Functional programming in Javascript is an antipattern

Automate NPM Dependencies installation on Git Pull

What is your go to firearm for overnight camping? #camping read here: https://t.co/GdRs9rI3hg

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Upsert and Upsert all with JDBCTemplate and Cockroach DB

Transform operator in web flux

242. Valid Anagram — LeetCode(Python)

Pacific Atlantic Water Flow: Leetcode — Blind 75 (Graph)