题解 | #牛群的同构特征# 哈希表

牛群的同构特征

https://www.nowcoder.com/practice/290ad8e24e6f41db80cc8d0cec6af720

建立s到t以及t到s的哈希映射

遍历两个字符串,当双方都不存在某字符的映射关系时,加入映射;

如果某字符的映射关系在两个映射表中产生冲突,返回false

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param t string字符串
     * @return bool布尔型
     */
    bool isIsomorphic(string s, string t) {
        int n = s.size();
        if (n != t.size()) {
            return false;
        }
        unordered_map<char, char> stot; // s到t的映射
        unordered_map<char, char> ttos; // t到s的映射
        for (int i = 0; i < n; i++) {
            if (stot.count(s[i]) == 0 && ttos.count(t[i]) == 0) {
                stot[s[i]] = t[i];
                ttos[t[i]] = s[i];
            } else if (stot[s[i]] != t[i] || ttos[t[i]] != s[i]) {
                return false;
            }
        }
        return true;
    }
};

时间复杂度:O(n),n为字符串长度,需要遍历一次字符串

空间复杂度:O(n),存储两张哈希表

全部评论

相关推荐

有没有什么神仙小厂啊!想去,感觉对大厂去魅了
野猪不是猪🐗:小厂最大的问题就是,你不知道哪天公司就直接🈚️了。大厂被裁,拿着大厂履历也不难再找,小厂寄了那后面有没有人要你就不好说了
点赞 评论 收藏
分享
2024-11-24 06:03
柜面服务
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务