[E哈希] lc2744. 最大字符串配对数目(读题+哈希表)

文章目录

    • 1. 题目来源
    • 2. 题目解析

1. 题目来源

链接:2744. 最大字符串配对数目

2. 题目解析

充分暴露了读题能力的薄弱…

字符不相等…字符串长度固定为 2,全是小写字符…

其实这个题目的思路和 lc 第一题,两数之和 的思路完全一致。哈希直接做即可,不需要考虑字符串长度、限制之类的东西。


  • 时间复杂度

    O

    (

    n

    )

    O(n)

    O(n)

  • 空间复杂度

    O

    (

    1

    )

    O(1)

    O(1)


class Solution {
public:
    int maximumNumberOfStringPairs(vector<string>& words) {
        int res = 0;
        unordered_set<string> S;
        for (auto &s : words) {
            string t = s;
            reverse(t.begin(), t.end());
            if (S.count(t)) res ++ ;
            S.insert(s);
        }

        return res;
    }
};


// 初始版本,没考虑清楚
class Solution {
public:
    int maximumNumberOfStringPairs(vector<string>& words) {
        int res = 0;
        unordered_map<string, int> um;

        for (int i = 0; i < words.size(); i ++ ) {
            string tmp = words[i];
            reverse(tmp.begin(), tmp.end());

            um[tmp] = i + 1;
        }

        for (int i = 0; i < words.size(); i ++ ) {
            if (um[words[i]] > 0 && um[words[i]] - 1 != i)
                res ++ ;
        }

        return res / 2;
    }
};