[알고리즘] Isomorphic Strings

문제 정보

출처 : leetcode
난이도 : easy

[문제]
Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

[예제]
Input: s = "egg", t = "add"
Output: true

Input: s = "foo", t = "bar"
Output: false

내풀이

처음 문제를 봤을 때, 어떻게 풀어야 할지 감을 잡지 못했다. 그래서 내가 처음 푼 답은 hashMap에 넣고 key값을 찾아서 value와 비교하고 또 value를 찾아서 그 key값과 비교하는 엉망진창의 해답이었다.

class Solution {
    public boolean isIsomorphic(String s, String t) {
        
        Map<Character, Character> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(t.charAt(i)) && map.get(t.charAt(i)) != s.charAt(i)) {
                return false;
            } else if (map.containsValue(s.charAt(i))) {
                for (Map.Entry<Character, Character> mp : map.entrySet()) {
                    if (mp.getValue().equals(s.charAt(i)) && !mp.getKey().equals(t.charAt(i))) {
                        return false;
                    }
                }    
            }

            map.put(t.charAt(i), s.charAt(i));
        }

        return true;
    }
}

Runtime : 123 ms
Memory : 44.9 MB

개선하기

문제 해결법이 도저히 생각나지 않아서, leetcode의 Editorial을 참고했다.
일단 위 문제는 s와 t를 직접적으로 비교하는 문제가 아니라, s와 t의 패턴을 비교하는 문제로 접근해야했다. 'egg'는 숫자로 패턴을 만들면 '122', 'add' 또한 '122'로 첫번째 예제는 true를 반환한다. 이렇게 두 String의 패턴을 만든 후에 두 패턴이 같은지 비교하면 아래와 같은 코드가 나온다.

class Solution {
    public boolean isIsomorphic(String s, String t) {
       return transformString(s).equals(transformString(t));
    }

    private String transformString(String s) {
        Map<Character, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();

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

            sb.append(map.get(sChar));
            sb.append(" ");
        }

        return sb.toString();
    }
}

Runtime : 18 ms
Memory : 45.2 MB

처음 내가 푼 답은 시간복잡도가 O(N^2)이 나오지만, 아래는 O(N)이 나온다. Runtime 또한 많이 줄어든 것을 볼 수 있다.