한시온·2022년 9월 29일
0

# Description

Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

# Examples

Example 1:

Input: s = "egg", t = "add"
Output: true
Example 2:

Input: s = "foo", t = "bar"
Output: false
Example 3:

Input: s = "paper", t = "title"
Output: true

# Solution

class Solution {
public:
bool isIsomorphic(string s, string t) {
map<char, char> map, map_reversed;

for (int i = 0; i < s.size(); ++i) {
char& key = s[i];
char& val = t[i];

if (map.count(key) && map[key] != val) {
return false;
}
map.insert({key, val});
}

for (auto pair : map) {
const char key = pair.first;
char& val = pair.second;

if (map_reversed.count(val) && map_reversed[val] != key) {
return false;
}
map_reversed.insert({val, key});
}
return true;
}
};

# Explanation

## Pseudocode

procedure isIsomorphic(S, T)
define M, N

for i:=0 to size of S do
K <- S[i]
V <- T[i]
if K exists in M and M[K] != V then
return false
else do
M[K] <- V
end if
end for

for each pair in M do
K <- key of pair
V <- value of pair
if V exists in N and N[V] != K then
return false
else do
insert pair into N in reverse order
end if
end for

return true
end procedure

## Handling Exceptions

There are two cases that are not allowed in isomorphic strings.
1. When two same characters map to the different characters.
2. When two different characters map to the same character.

# Reference

https://leetcode.com/problems/isomorphic-strings/

가볍고 무겁게