[C++] LeetCode : Isomorphic Strings

| Question

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가 주어졌을 때 두 문자열이 isormorphic인지 판단하는 함수를 작성하라.

 

isormorphic의 조건은 아래와 같다.

• 문자열 s의 일부 문자를 교체했을 때 t로 만들 수 있어야 한다. 
• 만약 s의 문자열의 일부 문자 a를 b로 교체했을때 t가 된다면 isormorphic이다. 
• a를 b로 교체하기로 했다면 다른 문자는 b로 교체할 수 없고, a가 또 다른 문자열로 교체될 수도 없다.

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

 

제약사항

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

---

| Solution

문제를 풀 때 고려한 사항

• s and t consist of any valid ascii character. this means there can be another chracter except english spell.
• ascii code 범위 내 이기 때문에 size 256개 짜리 배열을 사용하거나, hash를 사용하면 될 것 같다. 

---

Method 1

1. s를 기준으로 char 하나에 t의 char를 대칭 시킨다. 
    1-1. s를 기준으로 쌍을 이루는게 이미 있는 경우, 그 값이 같으면 넘어가고 다르면 false를 return 한다.
    1-2. s를 기준으로 쌍을 이루는게 없는 경우
        1-2-1 그 값이 이미 다른 char에 대칭이 되었는지 확인한다. 대칭된 게 있으면 false 
        1-2-2 대칭된게 없으면 쌍으로 만들어준다. 

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char, char> my_map;
        bool paired[256] = {0};

        for(int i = 0; i < s.length(); i++) { 
            if(my_map.find(s[i]) != my_map.end()) {
                if(my_map[s[i]] != t[i]) return false;
            } else { 
                if(paired[t[i]] == true){
                    return false;
                }else{
                    my_map[s[i]] = t[i];
                    paired[t[i]] = true;
                }
            }
        }

        return true;
    }
};

• Time complexity : O(s) 
• Space Complexity : O(1) 

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

Isomorphic Strings - LeetCode