沉迷算法,无法自拔。

同构字符串

给定两个字符串 s 和 t,判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。

示例 1: 输入: s = "egg", t = "add" 输出: true 

示例 2: 输入: s = "foo", t = "bar" 输出: false 

示例 3: 输入: s = "paper", t = "title" 输出: true

解法一:

字符串中的字符一一对应?那就采用 HashMap 啊。HashMap 是一个散列表,它存储的内容是键值对(key-value)映射。用 s 中的字符对应 t 中的字符。如果映射正确,就返回 true ,否则返回 false 。

Java 代码:

public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length()) return false;
    Map<Character, Character> map = new HashMap<>();
    
    for (int i = 0; i < s.length(); ++i) {
        char ss = s.charAt(i), tt = t.charAt(i);
        if (map.containsKey(ss)) {
            if (map.get(ss) != tt) return false;
        } else {
            if (map.containsValue(tt)) return false;
            map.put(ss, tt);
        }
    }
    return true;
}

首先判断两个输入 s 和 t 的长度,不同直接返回 false 。然后创建哈希表,遍历字符串,如果存在 Key 则判断 Value 是否相同;如果不存在 Key 则判断Value 是否存在。循环完成后,如果没有返回 false 那就返回 true 。

得益于 HaseMap 的数据结构,真个函数执行的效率还是非常高效的。在测试用例下,耗时 20ms 消耗 36.8MB 。

解法二:

​是否有更高效的解法呢?毕竟 HashMap 再快再高效也不敌 Java  中的 八种基本类型间的运算。

我们注意到,ASCII 的编码中,字符的排序是 0~127 的,所以字符串 s 和 t 中的字符范围也在 0~127 之间。如果我们构建一个长度为 256 的字符数组,然后根据 +- 128 确定前后对应关系。不就可以省略 HashMap 了吗?

Java 代码:

public boolean isIsomorphic(String s, String t) {
    char[] ss = s.toCharArray(), tt = t.toCharArray(), map = new char[256];
    if (ss.length != tt.length) return false;
    for (int i = ss.length - 1; i >= 0; --i) {
        if (map[ss[i]] != map[tt[i] + 128]) {
            return false;
        }
        map[ss[i]] = map[tt[i] + 128] = ss[i];
    }
    return true;
}

new char[256] 创建出来的是256个 “\u0000” 是 NUL 。然后依旧判断长度,不同长度的直接 false 。然后遍历字符串,检测字符(ASCII 中 ‘a' = 97)判断前后是否相等,如果不等就 false , 相等的话就将这一关系同步到 map[n] 和 map[n+128]。然后一直循环直到结束,返回 true 。

利用这个精巧的结构,大大节约了运行时间:耗时 2ms , 消耗 26.7MB。