[LeetCode] 389. Find the Difference - 문제풀이

Description

s문자열을 무작위로 섞은뒤 하나의문자열을 추가해 만든 t가 있을때 추가된 문자를 구하는 문제입니다.

You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

Example 1:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:

Input: s = "", t = "y"
Output: "y"

Constraints:

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s and t consist of lowercase English letters.

Solution 1. 정렬(sort)

public char findTheDifference(String s, String t) {

    // 1. sort
    char[] sc = s.toCharArray();
    char[] st = t.toCharArray();
    Arrays.sort(sc);
    Arrays.sort(st);

    for (int i = 0; i < s.length(); i++) {
        if(sc[i] !=  st[i]){
            return st[i];
        }
    }
    return st[t.length()-1];
}

정렬을 이용한 방법입니다. 정렬 후 문자열을 비교하여 틀린경우 추가되는 문자열이므로 반환합니다.

Solution 2. Hash Table

public char findTheDifference(String s, String t) {

// 2. hash Table
    int[] map = new int[26];
    for(char c : s.toCharArray()){
        map[c-'a']++;
    }

    for(char c : t.toCharArray()){
        if(--map[c-'a'] == -1) return c;

    }
    return 'a';
}

Hash Table을 이용하여 기준 문자열의 문자별 카운팅을 한 뒤 t와 비교하여 하나씩 제외해 나갑니다. -가 된다면 s에서 사용된 문자보다 더 사용된 문자이므로 해당 문자를 반환합니다.

Solution 3. bit manipulation

public char findTheDifference(String s, String t) {

    // 3. bit manipulation
    int n = t.length();
    char c = t.charAt(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        c ^= s.charAt(i);
        c ^= t.charAt(i);
    }
    return c;
}

bit를 xor로 연산하며 비교해 나가는 방법입니다. 두개의 문자열을 반전시켜 나가면 결국 차이나는 문자열에 대한 연산만 남게됩니다.

x ^ x = 0

x ^ 0 = x

Reference

Find the Difference - LeetCode