[leetcode #389] Find the Difference

Problem

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.

Idea

주어진 문자열 s의 문자를 섞은 뒤 임의의 한 문자를 더한 문자열이 t라고 한다. 이 때 문자열 t에 더해진 임의의 문자가 무엇인지 확인하는 문제다.

Set을 쓰면 간단하게 풀 수 있지만 Space Complexity가 O(n)이 되므로 알파벳 수만큼 array를 만들어 갯수를 세면 Space Complexity를 O(1)로 하고 풀 수 있다.

우선 문자열 s를 탐색하면서 각 알파벳의 빈도를 센다. 이후 문자열 t를 탐색하면서 알파벳의 빈도를 하나씩 뺀다. 알파벳의 갯수를 저장한 배열을 탐색하면서 빈도가 0이 아닌 알파벳이 발견되면 곧바로 리턴하면 된다.

Solution

class Solution {
    public char findTheDifference(String s, String t) {
        int[] countS = new int[26];

        for (int i=0; i < s.length(); i++) {
            countS[s.charAt(i) - 'a']++;
        }

        for (int i=0; i < t.length(); i++) {
            countS[t.charAt(i) - 'a']--;
        }

        for (int i=0; i < countS.length; i++) {
            if (countS[i] != 0) {
                return (char) ('a' + i);
            }
        }

        return 'a';
    }
}

Reference

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