This is classified as a hard puzzle: https://leetcode.com/problems/palindrome-pairs/
palindrome-pairs-leetcode-online-judge
A palindrome string is a string whose reverse string is exactly the same, e.g. ABBA, 1, UIU…
Brute Force
Almost every puzzle has a bruteforce solution and this one is no exception. If the number of words given is N and the average word length is K, the following native solution has complexity O(N*N*K).
You would first need to define a function to check any given string is a palindrome.
1 2 3 4 5 6 7 8 9 | bool check(string s) { int len = s.length(); for (int i = 0; i < len / 2; i ++) { if (s.at(i) != s.at(len - i - 1)) { return false; } } return true; } |
bool check(string s) {
int len = s.length();
for (int i = 0; i < len / 2; i ++) {
if (s.at(i) != s.at(len - i - 1)) {
return false;
}
}
return true;
}The idea is to check from the start of the string until the middle so that each letter needs to match the letter at the other side of the string. This complexity is O(K) where K is the average length of the words. Note, the big O notation omits the constant part so O(K/2) becomes O(K).
Checking turn by turn between any two words gives the following algorithm:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | vector<vector<int>> palindromePairs(vector<string>& words) { vector<vector<int>> r; int len = words.size(); for (int i = 0; i < len - 1; i ++) { for (int j = i + 1; j < len; j ++) { string a = words[i] + words[j]; string b = words[j] + words[i]; if (check(a)) { vector<int> x(2, 0); x[0] = i; x[1] = j; r.push_back(x); } else { if (a != b) { if (check(b)) { vector<int> x(2, 0); x[0] = j; x[1] = i; r.push_back(x); } } } } } return r; } |
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> r;
int len = words.size();
for (int i = 0; i < len - 1; i ++) {
for (int j = i + 1; j < len; j ++) {
string a = words[i] + words[j];
string b = words[j] + words[i];
if (check(a)) {
vector<int> x(2, 0);
x[0] = i;
x[1] = j;
r.push_back(x);
}
else {
if (a != b) {
if (check(b)) {
vector<int> x(2, 0);
x[0] = j;
x[1] = i;
r.push_back(x);
}
}
}
}
}
return r;
}If this approach is accepted, it would not be hard at all. We can also store the check results but that would not be so much helpful because it is not so likely that same string will be checked again and again. The following still gives Time out Exceeded error.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | vector<vector<int>> palindromePairs(vector<string>& words) { vector<vector<int>> r; int len = words.size(); map<string, bool> cache; for (int i = 0; i < len - 1; i ++) { for (int j = i + 1; j < len; j ++) { string a = words[i] + words[j]; string b = words[j] + words[i]; bool aa; if (cache.count(a)) { aa = cache[a]; } else { aa = check(a); cache[a] = aa; } if (aa) { vector<int> x(2, 0); x[0] = i; x[1] = j; r.push_back(x); } if (a != b) { bool bb; if (cache.count(b)) { bb = cache[b]; } else { bb = check(b); cache[b] = bb; } if (bb) { vector<int> x(2, 0); x[0] = j; x[1] = i; r.push_back(x); } } } } return r; } |
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> r;
int len = words.size();
map<string, bool> cache;
for (int i = 0; i < len - 1; i ++) {
for (int j = i + 1; j < len; j ++) {
string a = words[i] + words[j];
string b = words[j] + words[i];
bool aa;
if (cache.count(a)) {
aa = cache[a];
} else {
aa = check(a);
cache[a] = aa;
}
if (aa) {
vector<int> x(2, 0);
x[0] = i;
x[1] = j;
r.push_back(x);
}
if (a != b) {
bool bb;
if (cache.count(b)) {
bb = cache[b];
} else {
bb = check(b);
cache[b] = bb;
}
if (bb) {
vector<int> x(2, 0);
x[0] = j;
x[1] = i;
r.push_back(x);
}
}
}
}
return r;
}Active Palindrome Construction
The above O(N*N*K) solution may pass but is on the verge of TL. We may need to think of a different solution. First of all, considering the following example:
[“BOT”, “TO”, “OT”]
Let’s take the first word to start with. All possible prefixes for string “BOT” are “” (empty string), “B” (palindrome), “BO” and “BOT”. So if we take all palindrome prefixes and find their corresponding counterparts, which are “BOT” and “OT” respectively. Now we reverse these and see if they are in the list. In this case, “TO” is in the list so we know TO+BOT is a palindrome.
The same approach goes to suffix. And for any palindromes itself, you would need to exclude them because the same index cannot be used twice.
To reverse a string, you can use the following O(K) approach (returning a new copy of the string).
1 2 3 4 5 6 7 8 | string reverse(string s) { string r = s; int len = s.length(); for (int i = 0; i < len; i ++) { r[i] = s[len - i - 1]; } return r; } |
string reverse(string s) {
string r = s;
int len = s.length();
for (int i = 0; i < len; i ++) {
r[i] = s[len - i - 1];
}
return r;
}We need to store the word-index key pair in the dictionary (map or unordered_map) for fast access.
1 2 3 4 5 6 | int len = words.size(); unordered_map<string, int> dict; // put words in the dict for (int i = 0; i < len; i ++) { dict[words[i]] = i; } |
int len = words.size();
unordered_map<string, int> dict;
// put words in the dict
for (int i = 0; i < len; i ++) {
dict[words[i]] = i;
}The solution has a O(N*K*K) algorithm complexity (N is the number of words given and K is the number of average word size) so it is easily accepted. We count the empty string as one of the prefix but not the suffix otherwise we will have duplicates e.g. palindrome words itself can be counted multiple times.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | vector<vector<int>> palindromePairs(vector<string>& words) { vector<vector<int>> r; int len = words.size(); unordered_map<string, int> dict; // put words in the dict for (int i = 0; i < len; i ++) { dict[words[i]] = i; } vector<int> match(2, 0); for (int i = 0; i < len; i ++) { string word = words[i]; // empty prefix string s = reverse(word); if (s != word) { // to exclude same index if (dict.count(s)) { match[0] = i; match[1] = dict[s]; r.push_back(match); } } int word_len = word.length(); // prefix for (int j = 0; j < word_len; j ++) { string prefix = word.substr(0, j + 1); if (check(prefix)) { string rest = reverse(word.substr(j + 1)); if (dict.count(rest)) { match[1] = i; match[0] = dict[rest]; r.push_back(match); } } } // suffix for (int j = word_len - 1; j >= 0; j --) { string suffix = word.substr(j); if (check(suffix)) { string rest = reverse(word.substr(0, j)); if (dict.count(rest)) { match[0] = i; match[1] = dict[rest]; r.push_back(match); } } } } return r; } |
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> r;
int len = words.size();
unordered_map<string, int> dict;
// put words in the dict
for (int i = 0; i < len; i ++) {
dict[words[i]] = i;
}
vector<int> match(2, 0);
for (int i = 0; i < len; i ++) {
string word = words[i];
// empty prefix
string s = reverse(word);
if (s != word) { // to exclude same index
if (dict.count(s)) {
match[0] = i;
match[1] = dict[s];
r.push_back(match);
}
}
int word_len = word.length();
// prefix
for (int j = 0; j < word_len; j ++) {
string prefix = word.substr(0, j + 1);
if (check(prefix)) {
string rest = reverse(word.substr(j + 1));
if (dict.count(rest)) {
match[1] = i;
match[0] = dict[rest];
r.push_back(match);
}
}
}
// suffix
for (int j = word_len - 1; j >= 0; j --) {
string suffix = word.substr(j);
if (check(suffix)) {
string rest = reverse(word.substr(0, j));
if (dict.count(rest)) {
match[0] = i;
match[1] = dict[rest];
r.push_back(match);
}
}
}
}
return r;
}–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: SQL Coding Exercise - Find Department Highest Salary
Next Post: C++ Coding Exercise - Self Crossing
