Problem
For 2 provided strings s1 and s2 we need to check if these strings are isomorphic. Two strings s1 and s2 are isomorphic if it is possible to derive the string s2 from the string s1 by mapping some of the s1 characters to other characters. And similarly, another way around, s1 should be derivable from s2.
Examples:
Input s1 | Input s2 | Output | Explanation |
abcdae | zbcdzy | true | If we replace a -> z and e -> y we can get s2 from s1. And vice versa, if we replace z -> a and y -> e we can get s1 from s2. |
cat | dog | true | if we replace c -> d, a -> o, t -> g we can get s2 from s1. And vice versa. |
madc | mama | false | we could not derive mama => madc because the 2nd m could not be mapped to d (it is already mapped to itself m -> m). |
acc | abd | false | we could not derive acc => abd because the 2nd c could not be mapped to d (it is already mapped to b). |
Solution
fn is_isomorphic_strings(s1: &str, s2: &str) -> bool {
if s1.len() != s2.len() {
return false;
}
let mut map1 = HashMap::new();
let mut map2 = HashMap::new();
s1.chars()
.zip(s2.chars())
.all(|(c1, c2)| match (map1.get(&c1), map2.get(&c2)) {
(Some(&c2_from_map1), _) if c2_from_map1 != c2 => false,
(_, Some(&c1_from_map2)) if c1_from_map2 != c1 => false,
_ => {
map1.insert(c1, c2);
map2.insert(c2, c1);
true
}
})
}
Explanation
One simple way to solve the puzzle is to use 2 auxiliary HashMaps: map1 and map2. We use all function to iterate over the zipped strings s1 and s2 at the same time (string characters c1 and c2 are available for use on each iteration) until on any iteration we encounter false result. On each iteration, we try to get c1 key from map1 and c2 key from map2.
If we have found c2_from_map1 character (mapped to c1 key) saved to the map1 earlier and this character does not equal the character c2 that we currently process (c2_from_map1 != c2), it means that the character c1 had already been mapped to another c2 character previously. In this case, we could return false concluding that the strings s1 and s2 are not isomorphic. A similar logic applies to the opposite case, where we check if the character c2 has already been mapped to another character c1.
Otherwise, we just insert c1 -> c2 to map1 and c2 -> c1 to map2.
Complexity
The time complexity of the solution is O(n) (where n is the length of the input strings).
The auxiliary space complexity is constant O(1) even though we used HashMaps to store characters. That is because the character set is fixed: though the input strings could be of any length, the set of characters they contain, which is stored in the maps, is limited. For ASCII characters, for example, it would not go beyond 128. In other words, the space needed to store characters in the map does not linearly depend on the length of the input strings.