PalindromePair-s1, C++ (gcc)

PalindromePair-s1

#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
    // M1: two loop check both (i,j) & (j,i )  n * n *L  
    // M2: Map
        // w1 = abcABA vs cba, or cba + ABAabc;
        // hashtable + 
        map<string, int> m; // word, idx
        vector<vector<int>> res;
        for(int i=0; i< (int) words.size(); i++)  m[words[i]] = i; 
        
        for(int i=0; i< (int) words.size(); i++){
            for(int len = 0; len <= (int)words[i].size(); len++){ // words[i] = s1 + s2; 
                string s1 = words[i].substr(0, len);
                string s2 = words[i].substr(len); 
                if(isPal(s1)) { // x+ s1+s2, find x 
                    string rv1 = reverse(s2); // 注意是反转哪个str
                    if(m.count(rv1) && m[rv1] != i){
                        res.push_back({m[rv1], i});
                    }
                }
                if(isPal(s2) && (int)s2.length()!=0  ) { // s1 + [s2] + y ， 注意边界条件 w+y
                    string rv2 = reverse(s1);
                    if(m.count(rv2) && m[rv2] != i){
                        res.push_back({i, m[rv2]}); 
                    }
                }
            }
        }
        return res; 
    }
    
private:
    string reverse(string& s){
        return string(s.rbegin(), s.rend());
    }
  
    bool isPal(string& s){
        if(s.length() <=1) return true;
        for(int i=0; i< (int) s.length()/2; i++){
            if(s[i] != s[s.length()-1-i]) return false;
        }
        return true;
    }
};

void print(vector<vector<int>>& v, vector<string>& w){
    for(auto x: v){
        cout << x[0] << " " << x[1] << " => " << (w[x[0]]+w[x[1]]) << endl; 
    }
    cout << endl;        
};
int main(){
    vector<string> words = {"abc", "cba", "cb"};
    Solution s;
    vector<vector<int>> res = s.palindromePairs(words); 
    print(res, words); 
    
    return 0;
}


run \| edit \| history \| help	0