[Easy] LeetCode - no.205 Isomorphic Strings : Java

https://leetcode.com/problems/isomorphic-strings/description/?envType=study-plan-v2&envId=top-interview-150

 

 

문제

String s와 t가 동형(isomorphic)인지 판별하는 문제

이 때 두 문자열이 동형이라는 것은, 각 문자가 서로 일대일로 매핑되어야 하며, 동일한 문자가 다른 위치에서도 동일하게 매핑되어야 함을 의미함

Example 1:
Input: s = "egg", t = "add"
Output: true
Explanation:The strings s and t can be made identical by:Mapping 'e' to 'a'.Mapping 'g' to 'd'.

Example 2:
Input: s = "foo", t = "bar"
Output: false
Explanation:The strings s and t can not be made identical as 'o' needs to be mapped to both 'a' and 'r'.

 

 

 

풀이1

import java.util.*;

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

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

            if (!map.containsKey(sc)) {
                boolean isOk = true;

                for (Map.Entry<Character, Character> entry : map.entrySet()) {
                    if (entry.getValue() == tc) {
                        isOk = false;
                    }
                }

                if (isOk) {
                    map.put(sc, tc);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                sb.append(map.get(c));
            } else {
                return false;
            }
        }

        if (sb.toString().equals(t)) {
            return true;
        }

        return false;
    }
}

• HashMap 사용
• sc와 tc를 각각 선언
• map이 sc라는 key값을 가지고 있지 않다면 map.entrySet()을 사용하여 tc라는 value값을 가지고 있지 않은지 확인
  • 둘 다 map에 존재하지 않는다면 map.put(sc, tc)
• StringBulider를 사용하여 s를 매핑하여 새로운 문자열을 만듦
  • 이 때 map에 존재하지 않는다면 false 반환 
• 위에서 만든문자열이 t와 동일하다면 true, 아니면 false 반환
• 시간복잡도 : O(N²)

💬 방법이 복잡하고 시간도 오래 걸리는 풀이

 

 

 

풀이2

  public boolean isIsomorphic2(String s, String t) {
    HashMap<Character, Integer> charIndexS = new HashMap<>();
    HashMap<Character, Integer> charIndexT = new HashMap<>();

    for (int i = 0; i < s.length(); i++) {
      if (!charIndexS.containsKey(s.charAt(i))) {
        charIndexS.put(s.charAt(i), i);
      }

       if (!charIndexT.containsKey(t.charAt(i))) {
        charIndexT.put(t.charAt(i), i);
      }

      if (!charIndexS.get(s.charAt(i)).equals(charIndexT.get(t.charAt(i)))) {
        return false;
      }
    }

    return true;
  }

• 2개의 HashMap 사용
• s와 t 각각의 char 값을 key로 하고, 인덱스 값(int)을 value로 함
• 둘의 인덱스 값을 비교하였을 때 서로 다를 경우 false 반환
• 시간복잡도 : O(N)

💬 좋은 풀이이긴 하지만 한 번에 와닿지 않고, 무엇보다 HashMap을 2개나 써야 함

 

 

 

풀이3

  public boolean isIsomorphic3(String s, String t) {
    HashMap<Character, Character> charMap = new HashMap<>();

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

      if (charMap.containsKey(sc)) {
        if (charMap.get(sc) != tc) {
          return false;
        }
      } else if (charMap.containsValue(tc)) {
        return false;
      }

      charMap.put(sc, tc);
    }

    return true;
  }

• HashMap 사용
• containsValue()를 사용하여 tc 값이 value로 포함되어 있는지 여부 확인 
• 시간복잡도 : O(N²)

💬 하나의 HashMap만으로 풀이 가능하지만, containsValue()는 시간복잡도가 최악의 경우 O(N)이기에 효율적이지 못함

다만 풀이1에 비해 코드 가독성이 나아졌고, 복잡성이 낮아짐