Time:5ms
- 第一次想用Map做,把所有字符串散列到Map里,然后再对两个字符串的散列结果进行比较,其实散列的思想是对的,只不过过程太复杂。
- 第二次想到用推进式的方法,边遍历边比较,这样应该比暴力遍历后再比较快,而且空间复杂度比较小,但是又犯了一个错误,用递归,结果就是进行了数万次递归后stackoverflow了。
- 第三次不递归了,但是还是超时,于是就判定用Map进行散列的方式太慢,还是用数组进行散列。
- 最后结果是,用数组散列可以,但是需要找到散列结果的比较方法。
public class Solution {
public boolean isIsomorphic(String s, String t) {
int[] sHash = new int[128];
int[] tHash = new int[128];
char[] sChars = s.toCharArray();
char[] tChars = t.toCharArray();
for (int i = 0; i < s.length(); i++) {
if (sHash[sChars[i]] != tHash[tChars[i]]) {
return false;
}
sHash[sChars[i]] += i + 1;
tHash[tChars[i]] += i + 1;
}
return true;
}
}
网友评论