[LeetCode] 205. Isomorphic Strings

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

Leetcode - Isomorphic Strings

문제 유형 : 해시 / 문자열 처리

문제 난이도 : Easy

 

문제

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.

 

두 문자열 s와 t가 주어진다.

s에서 다음의 변환을 해서 t를 얻을 수 있는지(같은 구조인지) 확인하시오:

s의 문자들은 다른 문자로 변환되어야 합니다. 

한 문자로 매핑되는 문자가 두 개 이상 되어서는 안됩니다. 자기 자신으로의 매핑은 가능합니다.

 

풀이

해시맵을 두 개 만든다. 하나는 매핑을 기록하는, 또 하나는 매핑되는 대상이 이미 매핑되었는지 확인을 위해서이다.

s의 문자들을 순차적으로 읽으면서 다음을 진행한다:

만약 s[i]가 처음 인식되는 문자라면, t[i]로 매핑시킨다.

그러나, t[i]로의 매핑이 이미 있다면, false를 반환한다.

s[i]가 처음 인식되는 문자가 아니라면, s[i]를 매핑 대상으로 매핑시킨다.

 

이제, s와 t가 같은지 비교한다.

 

코드

C++

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        const int n = s.size();
        unordered_map<char, char> mp;
        unordered_map<char, bool> mapped;


        for(int i = 0; i < n; i++) {
            if(!mp[s[i]]) {
                if(mapped[t[i]]) return false;
                mp[s[i]] = t[i];
                mapped[t[i]] = true;
            }

            s[i] = mp[s[i]];
        }

        return s == t;
    }
};