문제
- 문제 링크
- 두 문자열
s
와 t
가 주어진다. 두 문자열이 isomorphic
한지 알아내야 한다. isomorphic
하다는 건 두 문자열에서 같은 위치(인덱스)에 있는 문자들이 서로 대응되어 교체될 수 있는 상태이다. 예를 들어 a
라는 문자는 어떤 문자에든 대응될 수 있지만, 1:1로만 대응되어야 한다.
- egg와 add는 isomorphic 하다.
- badc와 baba는 isomorphic 하지 않다.
- 제약 조건
- 문자열 길이:
1 <= s.length <= 5 * 10^4
풀이
풀기 전
- 맵을 만들어서 특정 문자가 중복으로 다른 문자에 대응되지 않도록 하면 될 거 같았다.
- 처음에는 맵을 하나만 만들었는데, 테스트 코드 돌려보니 두개를 만들어서 양방향으로 체크해야 했다.
- 문자열 길이만큼 순회하니까
시간 복잡도는 O(s.length)
이고 최대 문자열 길이만큼 map에 저장하니까 공간 복잡도도 O(s.length)
이다.
코드
class Solution {
public boolean isIsomorphic(String s, String t) {
HashMap<Character, Character> map1 = new HashMap<>();
HashMap<Character, Character> map2 = new HashMap<>();
for (int i=0; i<s.length(); i++) {
Character ch1 = s.charAt(i);
Character ch2 = t.charAt(i);
if (!map1.containsKey(ch1)) {
map1.put(ch1, ch2);
}
if (!map2.containsKey(ch2)) {
map2.put(ch2, ch1);
}
if (map1.get(ch1) != ch2 || map2.get(ch2) != ch1)
return false;
}
return true;
}
}
푼 후
- 조금 마음에 안 들게 지저분한 코드이긴 하다.
- 다른 사람 코드 보니까 비슷한 아이디어에 넉넉한 배열 사용해서 풀었다.