[Leetcode Top Interview 150] 205. Isomorphic Strings

난이도 : easy

문제링크

• 두개의 문자열이 주어진다 : s, t
• s와 t가 isomorphic 한지 체크하라

 

• isomorphic은 다르게 표현되지만 같은 구조를 가지고 있을 때 사용한다
• s의 문자가 t의 문자로 replace될 수 있으면 isomorphic하다 할 수 있다
• ex) s="egg", t="add" => true
• ex) s="foo", t="bar" => false
• ex) s="paper", t="title" => true

 

1. 접근법

• 해시테이블 생성
  • s문자에 대응되는 t문자
  • t문자에 대응되는 s문자 
• 한 문자씩 순회하면서,
  • 특정 s문자에 대응되는 t문자가 해시테이블에서 가지고있는 값과 동등한지 확인
  • 특정 t문자에 대응되는 s문자가 해시테이블에서 가지고있는 값과 동등한지 확인

 

3. 구현 코드

class Solution {
    public boolean isIsomorphic(String s, String t) {        
        Map<Character, Character> mapS = new HashMap<>();
        Map<Character, Character> mapT = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char sc = s.charAt(i);
            char tc = t.charAt(i);

            if (!mapS.containsKey(sc)) {
                mapS.put(sc, tc);
            } else {
                if (!mapS.get(sc).equals(tc)) {
                    return false;
                }
            }

            if (!mapT.containsKey(tc)) {
                mapT.put(tc, sc);
            } else {
                if (!mapT.get(tc).equals(sc)) {
                    return false;
                }
            }
        }        

        return true;
    }
}

• s문자에 대응되는 t문자가 value로 존재하지 않으면
  • 해시테이블에 저장
• s문자에 대응되는 t문자가 value로 존재한다면
  
  • 현재 순회중인 t문자와 해시테이블의 s문자에 대한 value값과 동등한지 확인

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 데이터를 순회함
• 공간복잡도 : O(n) - 모든 데이터를 생성해야 함