[leetcode] Isomorphic Strings

·2024년 4월 2일
0

코딩

목록 보기
16/45

문제

  • 문제 링크
  • 두 문자열 st가 주어진다. 두 문자열이 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);  // s의 i번째 문자 가져온다.
            Character ch2 = t.charAt(i);  // t의 i번째 문자 가져온다.
            
            if (!map1.containsKey(ch1)) {  // s->t로 대응되는 문자가 없으면 새로 추가한다.
                map1.put(ch1, ch2);
            }
            if (!map2.containsKey(ch2)) {  // t->s로 대응되는 문자가 없으면 새로 추가한다.
                map2.put(ch2, ch1);
            }

			// 이미 대응되어 맵에 추가된 문자가 현재 대응되는 문자와 같지 않으면 false 반환한다.
            // 양방향으로 체크한다.
            if (map1.get(ch1) != ch2 || map2.get(ch2) != ch1)
                return false;
        }
        return true;
    }
}

푼 후

  • 조금 마음에 안 들게 지저분한 코드이긴 하다.
  • 다른 사람 코드 보니까 비슷한 아이디어에 넉넉한 배열 사용해서 풀었다.
profile
개발 일지

0개의 댓글