The best submission ever 256ms in C++, well-commented


  • 1
    class Solution 
    {
    private:
        bool isPal(string& s, int start, int end)  //start and end refer to index;
        {
            while(s[start] == s[end]) start++, end--;
            return start >= end;
        }
    
    public:
        //AC - 256ms;
        vector<vector<int>> palindromePairs(vector<string>& words) 
        {
            vector<vector<int>> result;
            if(words.empty()) return result;
            unordered_map<string, int> table; //words and its corresponding index;
            for(int i = 0; i < words.size(); i++) table[words[i]]=i;
            for(int i = 0; i < words.size(); i++) 
            {
                string cur = words[i], t_str;
                reverse(cur.begin(), cur.end());
                int t=0, len=cur.size();
                for(int l = 0; l <= len; l++) //l is the length of the sub-string;
                {
                    if(isPal(cur,0, l-1))  //the current word will work as prefix;
                    {
                        t_str = cur.substr(l);
                        if(table.count(t_str))  //accelerate the checking process;
                        {
                            t = table[t_str];
                            if((t!=i) && (len>=words[t].size())) //avoid duplicates;
                            result.push_back(vector<int>{i, t}); //the matched word will be the suffix;
                        }
                    }
                    if(isPal(cur, l, len-1)) //the current word will work as suffix;
                    {
                        t_str = cur.substr(0,l); 
                        if(table.count(t_str)) 
                        {
                            t = table[t_str];
                            if((t!=i) && (len>words[t].size())) //avoid duplicates;
                            result.push_back(vector<int>{t, i}); //the matched word the prefix;
                        }
                    }
                }
            }
            return result;
        }
    };

  • 0

    Actually we do not need to check too much to avoid duplicates as I did in the previous post. After updating these parts, we can reach a more terse version in c++ as follows.

    class Solution {
    private:
        bool isPal(string& s, int l, int r){
            while(l<r && s[l]==s[r]) l++, r--;
            return l >= r;
        }
    public:
        vector<vector<int>> palindromePairs(vector<string>& words) {
            vector<vector<int>> vv;
            if(words.size() == 0) return vv;
            unordered_map<string, int> word_map;
            for(int i = 0; i < words.size(); ++i) word_map[words[i]] = i;
            for(int i = 0; i < words.size(); ++i){
                int len = words[i].length(), t;
                string cur = words[i], t_str;
                reverse(cur.begin(), cur.end());
                for(int l = 0; l <= len; ++l){
                    if(isPal(cur, 0, l-1)){
                        t_str = cur.substr(l);
                        if(word_map.count(t_str)){
                            t = word_map[t_str];
                            if(t!=i) vv.push_back(vector<int>{i, t});
                        }
                    }
                    if(isPal(cur, l, len-1)){
                        t_str = cur.substr(0, l);
                        if(word_map.count(t_str)){
                            t = word_map[t_str];
                            if(len>l) vv.push_back(vector<int>{t, i});
                        }
                    }
                }
            }
            return vv;
        }
    };
    

Log in to reply
 

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