Accepted native brute force solution


  • 0
    J

    the idea is just to loop to check <i,j> string ,whether w[i]+w[j] can be palindrome,
    the difference is we skip the string concatenation , directly check the palindrome based on i and j string, seems very quick in ac test

    bool palindrome(string &s,string &t){
            int m = s.size(),n = t.size();
            int l = 0,r = n-1;
            while(l < m && r >= 0){
                if(s[l] != t[r])return false;
                l++,r--;
            }
            if(l < m){
                r = m-1;
                while(l < r){
                    if(s[l] != s[r])return false;
                    l++,r--;
                }
            }else {
                if(r >= 0){
                    l = 0;
                    while(l < r){
                        if(t[l] != t[r])return false;
                        l++,r--;
                    }
                }
            }
            return true;
        }
        //hash table
        vector<vector<int>> palindromePairs(vector<string>& words) {
                            vector<vector<int>>res;
                            for(int i = 0;i < words.size();i++){
                                for(int j=0;j < words.size();j++){
                                    if(i==j)continue;
                                    //two pointer
                                    if(palindrome(words[i],words[j])){
                                        res.push_back({i,j});
                                    }
                                }
                            }
                            return res;
        }
    

Log in to reply
 

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