容器的妙用: 判断两个字符串同构

一个架构师

发布于 2022-06-20 20:06:27

4790

给定两个字符串, 判断两个字符串的结构是否相同, 比如说abb与cdd就是同构的, ab与aa 就不是同构的.

同构也就意味着, 两个字符串中的每一位是能够一一对应, 存在映射关系的.

以abb与cdd为例

a -> c
b -> d

需要选择一个合适的容器去存储映射关系, 通常会选用HashMap.

还需要注意的是ab与aa 中b映射a的情况,

a已经映射到a了,

b再次映射a时, 就已经打乱映射关系了, 不能算同构了.

所以, 还需要另外一个容器, 记录已经映射过的字符, 通常会选用HashSet;

代码如下:

public static boolean isIsomorphic(String s, String t) {
  Map<Character, Character> map = new HashMap();
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i), c2 = t.charAt(i);
            Character ch = map.get(c1);
            if (ch == null) {
                if(!set.contains(c2)){
                    map.put(c1, c2);
                    set.add(c2);
                } else {
                    return false;
                }
            } else if (ch.charValue() != c2) {
                return false;
            }
        }
        return true;
    }

这是个很简单的算法, 今天拿出来分享是因为它代表着一种解题思路:

在解决一些需要记录映射关系或者遍历记录时, 可以选择其他O(1)复杂度的容器, 辅助解决, 达到空间换时间的目的.

这些O(1)复杂度的容器通常是HashMap和HashSet.

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-08-17，如有侵权请联系 cloudcommunity@tencent.com 删除

容器