Advertisement
nikunjsoni

336

Jun 13th, 2021
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. class Solution {
  2.  public:
  3.      vector<vector<int>> palindromePairs(vector<string>& words) {
  4.          unordered_map<string, int> dict;
  5.          vector<vector<int>> ans;
  6.          // build dictionary
  7.          for(int i = 0; i < words.size(); i++) {
  8.              string key = words[i];
  9.              reverse(key.begin(), key.end());
  10.              dict[key] = i;
  11.          }
  12.          // edge case: if empty string "" exists, find all palindromes to become pairs ("", self)
  13.          if(dict.find("") != dict.end()){
  14.              for(int i = 0; i < words.size(); i++){
  15.                  if(i == dict[""]) continue;
  16.                  if(isPalindrome(words[i])) ans.push_back({dict[""], i}); // 1) if self is palindrome, here ans covers concatenate("", self)
  17.              }
  18.          }
  19.  
  20.          for(int i = 0; i < words.size(); i++) {
  21.              for(int j = 0; j < words[i].size(); j++) {
  22.                  string left = words[i].substr(0, j);
  23.                  string right = words[i].substr(j, words[i].size() - j);
  24.  
  25.                  if(dict.find(left) != dict.end() && isPalindrome(right) && dict[left] != i) {
  26.                      ans.push_back({i, dict[left]});     // 2) when j = 0, left = "", right = self, so here covers concatenate(self, "")
  27.                  }
  28.  
  29.                  if(dict.find(right) != dict.end() && isPalindrome(left) && dict[right] != i) {
  30.                      ans.push_back({dict[right], i});
  31.                  }
  32.              }
  33.          }
  34.          return ans;        
  35.      }
  36.  
  37.      bool isPalindrome(string str){
  38.          int i = 0;
  39.          int j = str.size() - 1;
  40.  
  41.          while(i < j) {
  42.              if(str[i++] != str[j--]) return false;
  43.          }
  44.          return true;
  45.      }
  46.  
  47.  };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement