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

Best of both worlds: Serverless Cloud + Next.js

PatternFly Roadmap Update

The PatternPast visual logo. It reads “PatternFly vintage blog, established 2015.”

Angular server-side rendering with @ng-toolkit/universal

Clean Code Applied to JavaScript (Part 7: Practical Refactoring)

Babel under the hood.

Understanding the Observer Design Pattern

Figurine and headphones on a desk

What’s the deal with passing strings into the JavaScript Date constructor?

Rapid prototyping with the expo-starter kit

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

Epam Interview Experience(12/27/2021)

Minimum Depth of Binary Tree

Creating prefix sum

Scholar @ SAP Labs interview experience