三刷 08/2022
Version #3 Store the mapping
Time O(N)
Space O(256) ~ O(1)
Runtime: 7 ms, faster than 83.52% of Java online submissions for Isomorphic Strings.
Memory Usage: 43 MB, less than 52.59% of Java online submissions for Isomorphic Strings.
class Solution {
public boolean isIsomorphic(String s, String t) {
if (s == null && t == null) {
return true;
}
if (s == null || t == null) {
return false;
}
if (s.length() != t.length()) {
return false;
}
Character[] map = new Character[256];
Set<Character> used = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
char sc = s.charAt(i);
char tc = t.charAt(i);
if (map[sc] != null) {
if (map[sc] != tc) {
return false;
}
continue;
}
if (used.contains(tc)) {
return false;
}
map[sc] = tc;
used.add(tc);
}
return true;
}
}
Version #2 Normalize to the first occurrence of each character
Time O(N)
Space O(256) ~ O(1)
Runtime: 10 ms, faster than 65.22% of Java online submissions for Isomorphic Strings.
Memory Usage: 42.8 MB, less than 68.67% of Java online submissions for Isomorphic Strings.
class Solution {
public boolean isIsomorphic(String s, String t) {
if (s == null && t == null) {
return true;
}
if (s == null || t == null) {
return false;
}
if (s.length() != t.length()) {
return false;
}
Integer[] sIndex = new Integer[256];
Integer[] tIndex = new Integer[256];
for (int i = 0; i < s.length(); i++) {
char sc = s.charAt(i);
char tc = t.charAt(i);
if (sIndex[sc] == null) {
sIndex[sc] = i;
}
if (tIndex[tc] == null) {
tIndex[tc] = i;
}
if (sIndex[sc] != tIndex[tc]) {
return false;
}
}
return true;
}
}
Version #2 Normalize string to array of int index
2.38 %
class Solution {
public boolean isIsomorphic(String s, String t) {
// char can be replaced by the index of its first occurance
if (s == null || t == null) {
return false;
}
return Arrays.equals(normalize(s), normalize(t));
}
private int[] normalize(String str) {
Map<Character, Integer> hash = new HashMap<>();
return IntStream.range(0, str.length()).map(i -> {
char c = str.charAt(i);
if (hash.containsKey(c)) {
return hash.get(c);
} else {
hash.put(c, i);
return i;
}
}).toArray();
}
}
一刷
Version #1
"The main idea is to store the last seen positions of current (i-th) characters in both strings. If previously stored positions are different then we know that the fact they're occurring in the current i-th position simultaneously is a mistake."
We're using the Arrays.fill() function to initialize the index arrays with -1 to indicate that the characters are not touched. Otherwise we can't distinguish if a index is 0 or have not been seen before.
87.70%
public class Solution {
public boolean isIsomorphic(String s, String t) {
if (s == null || t == null || s.length() != t.length()) return false;
int[] sLastIndex = new int[256];
int[] tLastIndex = new int[256];
Arrays.fill(sLastIndex, -1);
Arrays.fill(tLastIndex, -1);
for (int index = 0; index < s.length(); index++) {
char sChar = s.charAt(index);
char tChar = t.charAt(index);
if (sLastIndex[sChar] != tLastIndex[tChar]) return false;
sLastIndex[sChar] = index;
tLastIndex[tChar] = index;
}
return true;
}
}
No comments:
Post a Comment