题目来源：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 数组效率更高？