LeetCode 205. Isomorphic Strings [Easy]

发表于 | 更新于 | 分类于 ， | 阅读次数：

题目来源：https://leetcode.com/problems/isomorphic-strings

题目难度：Easy

解答1[Java]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] m1 = new int[256]; 
        int[] m2 = new int[256];
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (m1[s.charAt(i)] != m2[t.charAt(i)]) return false;
            m1[s.charAt(i)] = i + 1;
            m2[t.charAt(i)] = i + 1;
        }
        return true;

    }
}

思路

不直接建立字母之间的映射关系，而是把要建立映射关系的字母同时映射到另外一个数字。相当于建立了一个间接映射关系。

解答1小优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] m1 = new int[256];
        int[] m2 = new int[256];
        char[] sCharArray = s.toCharArray();
        char[] tCharArray = t.toCharArray();

        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (m1[sCharArray[i]] != m2[tCharArray[i]]) return false;
            m1[sCharArray[i]] = i + 1;
            m2[tCharArray[i]] = i + 1;
        }
        return true;

    }
}

反复调用 String 类的 charAt() 方法是比较慢的，优化之后运行总时间由 4ms 减为2ms。可能是函数调用也要占用一部分空间。而直接使用数组，除了数组的空间不需要额外的空间。

空间占用，两次调用，数值差距很大，不知道为什么。

解答2[Java]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean isIsomorphic(String s, String t) {
        char[] sString = s.toCharArray();
        char[] tString = t.toCharArray();

        int length = s.length();
        if (length != t.length())
            return false;

        char[] sMap = new char[256];
        char[] tMap = new char[256];

        for (int i = 0; i < length; i++) {
            char sChar = sString[i];
            char tChar = tString[i];

            if (sMap[sChar] == 0 && tMap[tChar] == 0) {
                sMap[sChar] = tChar;
                tMap[tChar] = sChar;
            } else if (sMap[sChar] != tChar || tMap[tChar] != sChar)
                return false;

        }
        return true;
    }
}

思路

这个算法是通过两个数组，两个数组对应两种映射关系。但是都是字符映射到字符的。

这个算法比上边使用 int 数组的算法要快。上边的算法优化之后是 2ms，但是这个算法是 1ms。

难道是因为使用 char 数组比使用 int 数组效率更高？