Leet Code - 205. Isomorphic Strings(C++)

예제: Isomorphic Strings

문제
Given two strings s and t, determine if they are isomorphic.

Two strings 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

풀이

주어진 문자 s와 t의 패턴이 같느냐 하는 문제이다.

처음에 필자는 알파벳의 증감도 같아야 하는 줄 알았다.
즉, "ba"와 "ac"는 다르다고 생각했다. b->a는 감소이고, a->c는 증가이니까. 그러나 증감은 상관이 없다.

따라서 필자는 숫자로 패턴을 만들며 비교하는 방법을 사용하였다.
예를 들어, ba->12, ac->12 이런 식으로 변환하는 것이다.

그러면 오답은 어떻게 체크 하느냐,
aa->11, ab->12가 되므로 두 번째 숫자 패턴에서 오답으로 결정나는 것이다.

전체적인 소스코드는 아래와 같다.

소스 코드

class Solution {
public:
	bool isIsomorphic(string s, string t) {
		int slen = s.size();
		int tlen = t.size();
		if (slen != tlen) return false;

		unordered_map<char, int> sm, tm;
		int scnt = 1, tcnt = 1;
		string sres, tres;

		for (int i = 0; i < slen; i++) {
			int& sint = sm[s[i]];
			if (!sint) {
				sres += (scnt + '0');
				sint = scnt;
				scnt++;
			}
			else {
				sres += sint;
			}

			int& tint = tm[t[i]];
			if (!tint) {
				tres += (tcnt + '0');
				tint = tcnt;
				tcnt++;
			}
			else {
				tres += tint;
			}

			if (sres[i] != tres[i])
				return false;
		}

		return true;
	}
};

풀이 후기

필자가 푼 방법은 평균적으로 절반정도의 속도를 내었다.
s와 t문자열을 문제 그대로 맵핑하여 푸는 방법도 있었고, 이를 비롯하여 정말 여러가지 방법이 존재하였다.