Clean C++ implementation


  • 10
    F
    class Solution {
    public:
        vector<vector<int>> palindromePairs(vector<string>& words) {
            vector<vector<int>> result;
            unordered_map<string, int> dict;
            for(int i = 0; i < words.size(); i++) {
                dict[words[i]] = i;
            }
            for(int i = 0; i < words.size(); i++) {
                for(int j = 0; j <= words[i].length(); j++) {
                    //check the suffix word
                    if(is_palindrome(words[i], j, words[i].size() - 1)) {
                        /** the suffix word can be null to all the word **/
                        string suffix = words[i].substr(0, j);
                        reverse(suffix.begin(), suffix.end());
                        if(dict.find(suffix) != dict.end() && i != dict[suffix]) {
                            result.push_back({i, dict[suffix]});
                        }
                    }
                    //check the prefix word 
                    if(j > 0 && is_palindrome(words[i], 0, j - 1)) {
                        string prefix = words[i].substr(j);
                        reverse(prefix.begin(), prefix.end());
                        if(dict.find(prefix) != dict.end() && dict[prefix] != i) {
                            result.push_back({dict[prefix], i});
                        }
                    }
                }
            }
            return result;
        }
        
        bool is_palindrome(string& s, int start, int end) {
            while(start < end) {
                if(s[start++] != s[end--]) {
                    return false;
                }
            }
            return true;
            
        }
    };

  • 0
    S

    @fight.for.dream very concise and clear code


  • 0
    T

    What about the testcase : ['aa', 'aaaaaa']. That should be return [[0,1], [1,0]]. But this algorithm seems return only [[1, 0]]


  • 0
    Z

    @tdphong The suffix and prefix are sequentially checked. So it will output both.


  • 0
    Z

    This solution can also be improved to allow duplicate strings. Just use a vector<int> as hashmap value. Then the outer loop should iterate through the hashmap keys. Also add one more logic to check if the duplicate string itself is a palindrome or not.


  • 0
    Z

    Beat 98.9%

    class Solution {
    public:
        vector<vector<int>> palindromePairs(vector<string>& words) {
            if (words.empty()) return {};
            vector<vector<int>> ret;
            unordered_map<string, vector<int>> map;
            for (int i = 0; i < words.size(); ++i) {
                map[words[i]].push_back(i);
            }
            for (auto &u : map) {
                if (u.second.size() > 1 && isPalindrome(u.first, 0, u.first.size() - 1)) {
                    for (int i = u.second.size() - 1; i > 0; --i) {
                        for (int j = i - 1; j >= 0; --j) {
                            ret.push_back({u.second[i], u.second[j]});
                            ret.push_back({u.second[j], u.second[i]});
                        }
                    }
                }
                for (int i = u.first.size(); i >= 0; --i) {
                    if (i != u.first.size() && isPalindrome(u.first, 0, i)) {
                        string prefix = u.first.substr(i + 1, u.first.size() - i);
                        reverse(prefix.begin(), prefix.end());
                        if (map.find(prefix) != map.end() && prefix != u.first)
                            for (int j : u.second)
                                for (int k : map[prefix])
                                    ret.push_back({k, j});
                    }
                    if (isPalindrome(u.first, u.first.size() - i, u.first.size() - 1)) {
                        string surfix = u.first.substr(0, u.first.size() - i);
                        reverse(surfix.begin(), surfix.end());
                        if (map.find(surfix) != map.end() && surfix != u.first)
                            for (int j : u.second)
                                for (int k : map[surfix])
                                    ret.push_back({j, k});
                    }
                }
            }
            return ret;
        }
    private:
        bool isPalindrome(const string &str, int begin, int end) {
            while (begin < end) {
                if (str[begin++] != str[end--])
                    return false;
            }
            return true;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.