题解 | 特殊城市

个人认为这道题的难点在于如何优化时间复杂度。

这道题最容易想到的解法就是将所有的城市名和州名都放在一个哈希表中，让后遍历这个哈希标表中存放的城市名，再提取他的前2个字符，再更所有的值相比，这样做的化会有2层循环，一层是依次取每一个城市名的子串，另一层是遍历所有州的州名，时间复杂度为O(n^2)无法通过本题.

要做的事就是要将O(n^2)变为O(n)。

想到每一次判断A,B是否为对称矩阵时都会 重新经历判断之前B和其他的元素是否为对称矩阵，所以就有了接下来的优化方案：

将哈希表的结构改变一下！

原来的是unordered_map<string,string>，无法记录州名和前缀名相互对称的元素的个数

改为unordered_map<string,unordered_map<string,int>>后，可以直接通过前缀码或者州码来查询到这种组合在之前的判断中有多少个相同的对称元素，省去了重复遍历的过程。

在下面的代码板块中，每输入一组city和state.

1.先提取city的前缀prefix,

2.再使用find判断哈希表中是否有这样的前缀和州码组合，如果有，就输出这个数，得到匹配的对称城市的数量，加到ans中，再将这个匹配的城市数+1，如果没有，count[prefix][state]++会将这个前缀和州码的组合加入到哈希表中，并且赋值1.

值得注意的是，哈希表count中的两个string类型的数都是只有两位字符的字符串.可以借此判断AB的前缀和州码之间的关系.

#include <iostream>
#include<unordered_map>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    int t = n;

    unordered_map<string, unordered_map<string, int>> count;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        string city, state;
        cin >> city >> state;
        string prefix = city.substr(0, 2);
        if (prefix == state) {
            continue;
        }
        if (count.find(state) != count.end() &&
            count[state].find(prefix) != count[state].end()) {
            ans += count[state][prefix];
        }

        count[prefix][state]++;
    }
    cout << ans;
}