同构字符串

发表于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

LeetCode每日一题，205. Isomorphic Strings

先看题目描述

r5VIPI.png

大意就是给定字符串 s 和 t，让我们判断 s 和 t 每个位置上的字符是否都一一对应，即满足双射的关系

算法和思路

哈希表

我们可以维护一张哈希表，以 s 中字符为键，以 t 中字符为值，不断更新这张哈希表，如果出现冲突(即当前下标 index 对应的字符 s[index] 已经存在于哈希表的 key 中但其对应的 value 不为 t[index] 或 s[index] 不在哈希表的 key 中但 t[index] 已存在于哈希表的 value 中)，则返回 false；若遍历完后也没出现冲突，则返回 true

算法源码

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isIsomorphic(String s, String t) {
        int len = s.length();
        char[] ss = s.toCharArray();
        char[] ts = t.toCharArray();
        Map<Character, Character> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            if (map.containsKey(ss[i])) {
                if (map.get(ss[i]) != ts[i]) {
                    return false;
                }
            } else {
                if (map.containsValue(ts[i])) {
                    return false;
                }
                map.put(ss[i], ts[i]);
            }
        }
        return true;
    }
}

上面这个代码是自己实现的，后来看运行效率比较好的代码，发现别人是使用数组代替哈希表，效率更高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isIsomorphic(String s, String t) {
        return canMap(s, t) && canMap(t, s);
    }

    private boolean canMap(String s, String t) {
        char[] ss = s.toCharArray();
        char[] ts = t.toCharArray();
        int[] map = new int[128];
        for (int i = 0; i < ss.length; i++) {
            if (map[ss[i]] == 0) {
                map[ss[i]] = ts[i];
            } else if (map[ss[i]] != ts[i]) {
                return false;
            }
        }
        return true;
    }
}