리트코드 - 205. Isomorphic Strings

리트코드 - 205. Isomorphic Strings

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

 

문제 설명

두 개의 문자열 s와 t가 주어졌을 때, 이들이 동형(isomorphic)인지 여부를 결정합니다.

두 문자열 s와 t가 동형인 경우, 문자열 s의 문자들을 문자열 t로 바꿀 수 있음을 의미합니다.

모든 문자의 발생은 다른 문자로 대체되어야 하며, 문자의 순서는 보존되어야 합니다. 두 문자가 동일한 문자로 매핑될 수는 없지만, 문자는 자기 자신으로 매핑될 수 있습니다.

 

의사코드

map = new HashMap set = new HashSet 반복문 시작 (s 한글자씩 순회)     c = s 한글자씩 char형으로 변환     c2 = s 한글자씩 char형으로 변환     if (map에 key=c가 null이면)         map에 key=c, value=c2 넣음         set에 c2 추가         if (map 크기 != set 크기)             false 리턴     else if (map에 key=c인 vlalue가 c2랑 다르면)         false리턴 반복문 종료 true 리턴

 

풀이코드

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

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

            if (map.get(c) == null) {
                map.put(c, c2);
                set.add(c2);
                if (map.size() != set.size()) {
                    return false;
                }
            } else if (map.get(c) != c2) {
                return false;
            }
        }
        return true;
    }
}

코드설명

Map을 이용하여 key와 value에 각각 s, t 문자열을 잘라서 넣는 방법으로 풀었다.

 

s의 한글자를 map의 key로 하여 이 값이 없는 경우 t의 한글자를 value로 넣는다.

만약 key값이 있으면 값을 꺼내서 c2랑 비교해서 다르면 false를 리턴한다.

 

이렇게하면 key에 대해서는 중복을 해결할 수 있는데 반대로 value에 대해서는 중복이 존재할 수 있다.

set을 만들어서 map에 value를 넣을때마다 set에도 추가해서, 두 크기가 다르면 false를 리턴하게 만들었다.

 

최종적으로 반복문을 잘 빠져나오면 true를 리턴하게 했다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

map을 사용하여 빠르게 풀었지만 배열을 사용해서도 풀수 있지 않을까 싶었다.

문제에서 제약조건이 아스키코드만 입력되므로, 아래와 같이 풀 수도 있다.

 

리팩토링

class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] ascArr = new int[128];
        int[] ascArr2 = new int[128];

        for (int i = 0; i < s.length(); i++) {
            if (ascArr[s.charAt(i)] != ascArr2[t.charAt(i)]) {
                return false;
            }
            ascArr[s.charAt(i)] = i + 1;
            ascArr2[t.charAt(i)] = i + 1;
        }
        return true;
    }
}

두 개의 아스키 배열을 만들어서, 두 값이 같지 않으면 false를 리턴하고 같다면 해당 문자열의 int번째의 값에 값을 넣는다.

값을 넣을 때에는 다른 배열의 값과 같지 않은 임의의 값을 넣으면 되는데, 일반적으로 i + 1로 넣기에 이렇게 넣었다.

i로 하지 않는 이유는 i = 0 일 때, 이미 배열 값이 0 이므로 문제가 발생하기 때문이다.

 

정리

두 문자열의 동형 비교 방법