神刀安全网

C++ Coding Exercise – Palindrome Pairs

This is classified as a hard puzzle: https://leetcode.com/problems/palindrome-pairs/

C++ Coding Exercise – Palindrome Pairs

palindrome-pairs-leetcode-online-judge

Apalindrome string is a string whose reverse string is exactly the same, e.g. ABBA, 1, UIU…

Brute Force

Almost every puzzle has abruteforce 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.

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:

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.

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 anypalindromes 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).

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.

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.

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–

GD Star Rating

loading…

1118 words

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » C++ Coding Exercise – Palindrome Pairs

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮