[Leetcode] Find the Difference

 

leetcode.com/problems/find-the-difference/

Find the Difference - LeetCode

그렇게 어려운 문제는 아니었다.

s 문자열에서 임의의 문자를 하나 추가해서 셔플링시킨 t 문자열을 보고 어떤 문자가 추가된건지 return 해주는 문제다.

 

하나하나 대조하면서 찾으려면 O(N^2) 이 걸리니까 Linear 하게 풀 수 있는 아이디어가 필요했음

일단 소문자 a-z 로 제한이 되니까 a-z 를 index 삼아서 s 에 있는 문자들을 counting 하고

t 에 있는 문자열을 돌면서 counting 된게 없으면 그 문자를 리턴해주도록 했다.

 

    public static char findTheDifference(String s, String t) {
        int[] letter = new int[26];
        char c = 0;
        for (int i = 0; i < s.length(); i++) {
            letter[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            c = t.charAt(i);
            if (letter[c - 'a'] == 0) {
                break;
            } else {
                letter[c - 'a']--;
            }
        }
        return c;
    }

 

더 최적화 할 방법이 있나? 시간복잡도는 O(N) 이 최적인것 같다. 어차피 한번은 훑어봐야 하니까

공간복잡도를 최적화 시켜보자. 기본 아이디어는 아래와 같다.

 

s 와 t 는 다른 문자가 1개 존재한다.

그럼 나머지 문자는 다 같다. 같으면 무시하는 로직이 뭐가 있지? XOR 개념이다

s : "ab"

t : "abc" 일 때 

a ^ a ^ b ^ b ^ c 를 하면 c만 남는다 두개씩 나온건 다 0으로 돌아가니까.

 

같은거 판단하는 로직은 XOR을 자주 쓰니까 기억해야지

최종 코드는 아래와 같다. 한번씩 돌면서 전체 문자를 XOR 시켜주면 남는 캐릭터만 리턴해준다

    public static char findTheDifference2(String s, String t) {
        char c = 0;
        for(int i = 0; i < t.length(); i++) { c ^= t.charAt(i); }
        for(int i = 0; i < s.length(); i++) { c ^= s.charAt(i); }
        return c;
    }

 

끄읏