diff options
Diffstat (limited to 'other/palindrome_pairs.cpp')
-rw-r--r-- | other/palindrome_pairs.cpp | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/other/palindrome_pairs.cpp b/other/palindrome_pairs.cpp new file mode 100644 index 0000000..8048069 --- /dev/null +++ b/other/palindrome_pairs.cpp @@ -0,0 +1,38 @@ +#include "leetcode.h" + +class Solution { +public: + vvd palindromePairs(vector<string> &words) { + unordered_map<string, int> um; + for (int i = 0; i < words.size(); i++) { + string x = words[i]; + reverse(x.begin(), x.end()); + um[x] = i; + } + vvd ans; + for (int j = 0; j < words.size(); j++) { + string str = words[j]; + for (int i = 0; i <= str.size(); i++) { + string prefix = str.substr(0, i), suffix = str.substr(i); + if (!prefix.empty() && isPalindrome(prefix) && um.count(suffix) && + j != um[suffix]) + ans.push_back({um[suffix], j}); + if (isPalindrome(suffix) && um.count(prefix) && j != um[prefix]) + ans.push_back({j, um[prefix]}); + } + } + return ans; + } + +private: + bool isPalindrome(string &str) { + int i = 0, j = str.size() - 1; + while (i < j) { + if (str[i] != str[j]) + return false; + i++; + j--; + } + return true; + } +}; |