Leetcode:336. palindrome pair

Title source

• leetcode：336. The palindrome is right

Title Description

class Solution {
    
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
    
        
    }
};

title

Analyze the amount of data

If violence matches ： $15\ast 10^5$, Can pass

Can I hash bucket count ？

Analyze the meaning of the question

from words Select any two words in the array , See if it can form a palindrome string , And return an index array that can form a palindrome string .

Be careful [0,1] and [1,0] It's different

violence （ Overtime ）

Exhausting $i,j$, Find all possible combinations . If it is a palindrome , Just put the corresponding $(i,j)$ Push the result array .

Time complexity $O((N^2)\ast L)$,$N$ It's the number of words ,$L$ Is the average length of words

class Solution {
    
    bool isPalindrome(std::string str){
    
        if(str.empty()){
    
            return true;
        }
        int i = 0, j = (int)str.size() - 1;
        while (i <= j){
    
            if(str[i] != str[j]){
    
                return false;
            }
            i++;
            j--;
        }
        
        return true;
    }
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
    
        vector<vector<int>> res;
        int N = words.size();
        for (int i = 0; i < N; ++i) {
    
            for (int j = 0; j < N; ++j) {
    
                if(i != j){
    
                    if (isPalindrome(words[i] + words[j])) res.push_back({
    i, j});
                }
            }
        }
        return res;
    }
};

class Solution {
    
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
    
        vector<vector<int>> result{
    };
        int const size = words.size();
        for (int i = 0; i < size; ++i) 
            for (int j = i + 1; j < size; ++j) 
              {
    
                if (ispalindrome(words[i], words[j]))
                    result.push_back(vector<int>({
    i,j}));
                if (ispalindrome(words[j], words[i]))
                    result.push_back(vector<int>({
    j,i}));                
              }
        return result;
    }
private:
    bool ispalindrome(string const & word_left, string const & word_right) {
    
        int const sizel = word_left.size();
        int const sizer = word_right.size();
        int l = 0; 
        int r = sizel + sizer - 1;
        while (l < r) {
    
            char left = (l < sizel) ? (word_left[l]) : (word_right[l - sizel]) ;
            char right = (r < sizel) ? (word_left[r]) : (word_right[r - sizel]);
            if (left != right) return false;
            ++l, --r;
        }
        return true;
    }
};

Enumerate prefixes and suffixes

• In order to find flipped words quickly , Let's turn the words over in advance , Save to hash table , And its corresponding index .

class Solution {
    
    bool isPalindrome(std::string str){
    
        if(str.empty()){
    
            return true;
        }
        int i = 0, j = (int)str.size() - 1;
        while (i <= j){
    
            if(str[i] != str[j]){
    
                return false;
            }
            i++;
            j--;
        }

        return true;
    }

public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
    

        int N = words.size();
        std::map<std::string, int> reverse_map;
        for (int i = 0; i < N; ++i) {
    
            auto word = words[i];
            std::reverse(word.begin(), word.end());
            reverse_map.insert({
    word, i});
        }

        vector<vector<int>> res;
        for (int i = 0; i < N; ++i) {
    
            std::string word = words[i];

            // Think of yourself as palindrome , There is "" when , It can form two pairs 
            auto it = reverse_map.find("");
            if(it != reverse_map.end() && (reverse_map[""] != i) && isPalindrome(word)){
    
                res.emplace_back(vector<int>{
    reverse_map[""], i});
                res.emplace_back(vector<int>{
    i, reverse_map[""]});
            }

            //  When you are not palindrome , You can form a pair with yourself in reverse order 
            if(!isPalindrome(word)){
      // abcd ----> dcba ---> abcd
                auto tmp = words[i];
                if(reverse_map.find(tmp) != reverse_map.end() && reverse_map[tmp] != i){
    
                    res.emplace_back(vector<int>{
    i, reverse_map[tmp]});
                }
            }

            //  Enumerate prefixes and suffixes 
            for (int j = 1; j <= word.size() - 1; ++j) {
    //  Split 
                auto left = word.substr(0, j); //  The left part 
                auto right = word.substr(j); //  The right part 

                //fb + [aa]bf
                if(isPalindrome(left) && reverse_map.find(right) != reverse_map.end() && reverse_map[right] != i){
    
                    res.emplace_back(vector<int>{
    reverse_map[right], i});   //  Palindrome on the left , On the right, you can find the flip and not yourself 
                }

                // af[cc] + fa
                if(isPalindrome(right) && reverse_map.find(left) != reverse_map.end() && reverse_map[left] != i){
    
                    res.emplace_back(vector<int>{
    i, reverse_map[left]});   //  Palindrome on the left , On the right, you can find the flip and not yourself 
                }
            }
        }

        return res;
    }
};