Leetcode 336 palindrome pair (palindrome string + hash)

The main idea of the topic ： Give me a set of strings , Output all the two string splicing can form a palindrome string combination
The sample input ：[“abcd”,“dcba”,“lls”,“s”,“sssll”]
Sample output ：[[0,1],[1,0],[3,2],[2,4]]
Ideas ： Enumerate all possible splices , Determine whether each splicing is a palindrome string ,TLE.
Violence code ：

class Solution {
    
private:
    bool isHuiWen(string a){
    
        int i = 0, j = a.size()-1;
        while (i < j){
    
            if (a[i] != a[j]) return false;
            i++;j--;
        }
        return true;
    }
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
    
        vector<vector<int>> ans;
        int len = words.size();
        for (int i = 0; i < len; i++){
    
            for (int j = i+1; j < len; j++){
    
                if (isHuiWen(words[i]+words[j])){
    
                    vector<int> t;t.push_back(i);t.push_back(j);
                    ans.push_back(t);
                }
                if (isHuiWen(words[j]+words[i])){
    
                    vector<int> t;t.push_back(j);t.push_back(i);
                    ans.push_back(t);
                }
            }
        }
        return ans;
    }
};

Optimization idea ： Suppose the concatenated string is $a,b$, Might as well set $len(a)>=len(b)$, If $a$ and $b$ The spliced string is a palindrome string , So the string $a$ Before $len(b)$ String is a string $b$ The transpose , And $a$ The remaining strings are also palindromes .
Implementation method ： Use $map<string,int>$ Record all strings and subscripts , For each string , Determine whether each substring is a palindrome string , Whether the transpose of the remaining part is the same as other strings
AC Code ：

class Solution {
    
private:
    map<string, int> mp;
    bool isHuiWen(string s, int a, int b){
    
        int i = a, j = b;
        while (i < j){
    
            if (s[i] != s[j]) return false;
            i++;j--;
        }
        return true;
    }
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
    
        vector<vector<int>> ans;
        int len = words.size();
        for (int i = 0; i < len; i++){
    
            mp[words[i]] = i;
        }
        for (int i = 0; i < len; i++){
    
            int m = words[i].size();
            for (int j = 0; j <= m; j++){
    
                if (isHuiWen(words[i], j, m-1)){
    
                    string t = words[i].substr(0, j);
                    reverse(t.begin(), t.end());
                    if (mp.count(t) && mp[t] != i){
    
                        ans.push_back(vector<int>{
    i, mp[t]});
                    }
                }
                if (j && isHuiWen(words[i], 0, j-1)){
    
                    string t = words[i].substr(j, m);
                    reverse(t.begin(), t.end());
                    if (mp.count(t) && mp[t] != i){
    
                        ans.push_back(vector<int>{
    mp[t], i});
                    }
                }
            }
        }
        return ans;
    }
};