13:T4e8,class Solution { public: bool isPalindrome(string& s, int left, int right) { while (left < right) { if (s[left++] != s[right--]) return false; } return true; } vector> palindromePairs(vector& words) { unordered_map dict; vector> ans; for(int i = 0; i < words.size(); i++) dict[words[i]] = i; for(int i = 0; i < words.size(); i++) { string w = words[i]; for(int j = 0; j <= w.size(); j++) { if(isPalindrome(w, 0, j - 1)) { string revSuffix = w.substr(j); reverse(revSuffix.begin(), revSuffix.end()); if(dict.count(revSuffix) && dict[revSuffix] != i) ans.push_back({dict[revSuffix], i}); } if(j != w.size() && isPalindrome(w, j, w.size() - 1)) { string revPrefix = w.substr(0, j); reverse(revPrefix.begin(), revPrefix.end()); if(dict.count(revPrefix) && dict[revPrefix] != i) ans.push_back({i, dict[revPrefix]}); } } } return ans; } };14:T44a,var palindromePairs = function(words) { const wordMap = new Map(); const res = []; words.forEach((word, i) => wordMap.set(word, i)); const isPal = (word, left, right) => { while (left < right) { if (word[left++] !== word[right--]) return false; } return true; }; for (let i = 0; i < words.length; i++) { const word = words[i]; for (let j = 0; j <= word.length; j++) { if (isPal(word, 0, j - 1)) { const revSuffix = word.slice(j).split('').reverse().join(''); if (wordMap.has(revSuffix) && wordMap.get(revSuffix) !== i) { res.push([wordMap.get(revSuffix), i]); } } if (j !== word.length && isPal(word, j, word.length - 1)) { const revPrefix = word.slice(0, j).split('').reverse().join(''); if (wordMap.has(revPrefix) && wordMap.get(revPrefix) !== i) { res.push([i, wordMap.get(revPrefix)]); } } } } return res; };

Time Complexity

Space Complexity