Palindrome Pairs: Efficient Algorithm and Implementation in Python and C++

function palindromePairs(words: string[]): number[][] {\n let result = [];\n let wordsR = [];\n for(let i = 0; i < words.length; i++){\n wordsR[i] = words[i].split('')\n .reverse()\n .join('');\n }\n for(let i = 0; i < words.length; i++){\n for(let j = 0; j < words.length; j++){\n if(i==j) {\n continue;\n }\n let longStr = '';\n let shortStr = '';\n if(words[i].length >= words[j].length ){\n longStr = words[i];\n shortStr = wordsR[j];\n }else{\n longStr = wordsR[j];\n shortStr = words[i];\n }\n if(longStr.slice(0,shortStr.length) === shortStr &&\n verify(longStr.slice(shortStr.length))){\n result.push([i,j]);\n }\n }\n }\n return result;\n}\nfunction verify(s){\n for(let i = 0, j=s.length-1;i < j;i++,j--){\n if(s[i] !== s[j]){\n return false\n }\n }\n return true;\n}//转换成C++内容：vector<vector> palindromePairs(vector& words) {\n vector<vector> result;\n vector wordsR;\n for(int i = 0; i < words.size(); i++){\n string reverseWord = words[i];\n reverse(reverseWord.begin(), reverseWord.end());\n wordsR.push_back(reverseWord);\n }\n for(int i = 0; i < words.size(); i++){\n for(int j = 0; j < words.size(); j++){\n if(i == j) {\n continue;\n }\n string longStr = '';\n string shortStr = '';\n if(words[i].length() >= words[j].length() ){\n longStr = words[i];\n shortStr = wordsR[j];\n }else{\n longStr = wordsR[j];\n shortStr = words[i];\n }\n if(longStr.substr(0,shortStr.length()) == shortStr &&\n verify(longStr.substr(shortStr.length()))){\n result.push_back({i,j});\n }\n }\n }\n return result;\n}\nbool verify(string s){\n int i = 0;\n int j = s.length()-1;\n while(i < j){\n if(s[i] != s[j]){\n return false;\n }\n i++;\n j--;\n }\n return true;\n}\n