题目

palindrome-pairs

算法

* 哈希set

* 哈希无set

代码

* 哈希set

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> res;
        unordered_map<string, int> m;
        set<int> s;
        for (int i = 0; i < words.size(); ++i) {
            m[words[i]] = i;
            s.insert(words[i].size());
        }
        for (int i = 0; i < words.size(); ++i) {
            string t = words[i];
            int len = t.size();
            reverse(t.begin(), t.end());
            if (m.count(t) && m[t] != i) {
                res.push_back({i, m[t]});
            }
            auto a = s.find(len);
            for (auto it = s.begin(); it != a; ++it) {
                int d = *it;
                if (isValid(t, 0, len - d - 1) && m.count(t.substr(len - d))) {
                    res.push_back({i, m[t.substr(len - d)]});
                }
                if (isValid(t, d, len - 1) && m.count(t.substr(0, d))) {
                    res.push_back({m[t.substr(0, d)], i});
                }
            }
        }
        return res;
    }
    bool isValid(string t, int left, int right) {
        while (left < right) {
            if (t[left++] != t[right--]) return false;
        }
        return true;
    }
};

* 哈希无set

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> res;
        unordered_map<string, int> m;
        for (int i = 0; i < words.size(); ++i) m[words[i]] = i;
        for (int i = 0; i < words.size(); ++i) {
            int l = 0, r = 0;
            while (l <= r) {
                string t = words[i].substr(l, r - l);
                reverse(t.begin(), t.end());
                if (m.count(t) && i != m[t] && isValid(words[i].substr(l == 0 ? r : 0, l == 0 ? words[i].size() - r: l))) {
                    if (l == 0) res.push_back({i, m[t]});
                    else res.push_back({m[t], i});
                }
                if (r < words[i].size()) ++r;
                else ++l;
            }
        }
        return res;
    }
    bool isValid(string t) {
        for (int i = 0; i < t.size() / 2; ++i) {
            if (t[i] != t[t.size() - 1 - i]) return false;
        }
        return true;
    }
};