# Rust Interview Puzzles: Isomorphic Strings

·

### 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 `HashMap`s: `map1` and `map2`. We use `all` function to iterate over the `zip`ped 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 `HashMap`s 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.

Rust Playground with this code