(Leet Code c++)Isomorphic Strings

205. Isomorphic Strings

 

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.

 

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

 

Constraints:

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s and t consist of any valid ascii character.

map을 활용한 문제 풀이.

주어진 s 문자열이 t 문자열로 교체될 수 있는지 확인해야 한다.

 

우선 s의 각 문자가 t의 각 문자로 치환되는 결과를 저장하는 m,

s 문자열에서 중복되는 문자가 있는지 확인하는 sMap,

t 문자열에서 중복되는 문자가 있는지 확인하는 tMap.

 

for문을 통해 문자를 순회.

sMap과 tMap에서 현재 순회하고 있는 문자를 조회한 적이 있는지 확인한다.

둘 다 false 상태이면 처음 순회하는 문자기 때문에 m[s[i]] = t[i]를 저장한다.

그리고 sMap과 tMap에서 해당 문자를 true로 바꿔 주도록 한다.

 

만약 조회한 적이 있다면 m[s[i]]에 t[i] 문자가 있는지 확인하면 된다.

다르다면 조건을 만족하지 않기 때문에 false 리턴.

 

for문을 모두 돌게 되면 조건을 만족하기 때문에 true를 리턴.

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char, char> m;
        map<char, bool> sMap;
        map<char, bool> tMap;
        
        for(int i = 0; i < s.size(); i++){
            if(!sMap[s[i]] && !tMap[t[i]]){
                m[s[i]] = t[i];
                sMap[s[i]] = true;
                tMap[t[i]] = true;
            }
            else{
                if(m[s[i]] != t[i]){
                    return false;
                }
            }
        }
        
        return true;
    }
};