Easy to understand C++ solution


  • 0
    A

    The idea is quite straightforward. To find the palindrome pair for each word, we have four cases to consider. Assume one word is s1 and its pair is s2, then we have:

    1. s1 is palindrome and s2 is empty, such as: ABA+""
    2. s1 is empty and s2 is palindrome, such as: ""+ABA
    3. left part of s1 is palindrome, rest part is equal to the reverse of s2, such as DC+ABACD
    4. right part of s1 is palindrome, rest part is equal to the reverse of s2, such as CDABA+DC

    In fact case 1, 2 are the special cases of 3,4.
    To find s2 in word list, one should use hash table to accelerate.
    Duplicates can be removed by using "set".

    vector<vector<int>> palindromePairs(vector<string>& words) {
            set<vector<int>> ans;
            unordered_map<string, int> map;
            for (int i = 0; i < words.size(); ++i) {
                string rw = words[i];
                reverse(rw.begin(), rw.end());
                map[rw] = i;
            }
            for (int i = 0; i < words.size(); ++i)
            for (int j = 0; j <= words[i].size(); ++j) {
                string s1, s2;
                s1 = (j == 0) ? "" : words[i].substr(0,j);
                s2 = (j == words[i].size()) ? "" : words[i].substr(j);
                if (isPalindrome(s1) && map.find(s2) != map.end() && map[s2] != i) 
                    ans.insert({map[s2], i});
                if (isPalindrome(s2) && map.find(s1) != map.end() && map[s1] != i) 
                    ans.insert({i, map[s1]});
            }
            vector<vector<int>> ret;
            ret.assign(ans.begin(), ans.end());
            return ret;
        }
        bool isPalindrome(string& s) {
            int l = 0, r = s.size()-1;
            while(l < r) {
                if (s[l++] != s[r--])
                    return false;
            }
            return true;
        }
    

Log in to reply
 

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