[LeetCode] Valid Anagram

https://leetcode.com/problems/valid-anagram/description/

 

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

 

Example 1:

Input: s = "anagram", t = "nagaram"

Output: true

Example 2:

Input: s = "rat", t = "car"

Output: false

 

Constraints:

• 1 <= s.length, t.length <= 5 * 104
• s and t consist of lowercase English letters.

---

The problem was to check whether two given strings contain the same kinds of characters in the same quantities.
At first, I simply created a Map to count each character,

then compared it with the other string while decreasing the counts to zero.

주어진 두 개의 문자열을 구성하는 하나하나의 글자들의 종류와 숫자가 일치하는지 확인하는 문제.

처음에는 단순하게 Map을 만들어서 글자별 수를 만들고, 나머지 문자열과 비교하면서 숫자를 하나씩 0으로 내렸다.

 

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        Map<Character, Integer> sMap = new HashMap();
        for(char ch:ss){
            if(sMap.containsKey(ch)){
                sMap.put(ch, (int)sMap.get(ch) + 1);
            }else{
                sMap.put(ch, 1);
            }
        }

        for(char ch:tt){
            if(!sMap.containsKey(ch)){
                return false;
            }
            if(sMap.containsKey(ch)){
                if(sMap.get(ch) == 0){
                    return false;
                }
                sMap.put(ch, (int)sMap.get(ch)-1);
            }
        }
        return true;
    }
}

 

But the time efficiency wasn’t very good, so I wondered if there might be a better way.

근데 시간효율이 그렇게 좋지는 않아서 뭔가 더 좋은 다른 방법이 없을까 하고 고민하던 중...

Since each char can be converted to an int,

I thought that if the sum of the converted values matched, the strings might contain the same characters!

char는 int로 변환이 가능하니 모든 문자의 int 변환값을 더한 게 같으면 같은 문자가 되지 않을까?!

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        int sum = 0;
        for(int i=0; i<s.length(); i++){
            sum += (int) s.charAt(i);
            sum -= (int) t.charAt(i);
        }
        
        return sum == 0;
    }
}

 

So I did like this,...

그래서 이렇게 만들었는데,

 

 

Of course, there had to be test cases that would break this approach…

그래, 당연히 있겠지 이걸 파훼할 테스트케이스가...

 

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        int xor = 0;
        int sum = 0;

        for(int i=0; i<s.length(); i++){
            sum += (int) s.charAt(i);
            sum -= (int) t.charAt(i);
            xor ^= s.charAt(i);
            xor ^= t.charAt(i);
        }
        
        return sum == 0 && xor == 0;
    }
}

 

To improve it, I even tried mixing in the bitwise XOR operator.

It passed most simple cases, but ultimately it couldn’t filter everything correctly.
So I decided to look for another method.

개선하기 위해 이런 식으로 비트 XOR 연산자까지 섞어서 해 봤는데, 웬만한 건 통과돼도 결국 완벽하게 거를 수는 없었다.

그냥 다른 방법을 찾아보기로...

 

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        int[] sArr = new int[26];

        for(int i=0; i<s.length(); i++){
            sArr[(int)s.charAt(i)-97]++;
        }
        for(int j=0; j<s.length(); j++){
            if(sArr[(int)t.charAt(j)-97] == 0){
                return false;
            }else{
                sArr[(int)t.charAt(j)-97]--;
            }
        }

        return true;
    }
}

 

In the end, I created an array based on lowercase English letters, counting each character with 'a' as the baseline.
Then, while iterating through the second string, I decreased the corresponding counts one by one.
This clearly improved the time efficiency.

In this problem, only lowercase English letters appear, so I didn’t add any special handling.

But if I want to cover other characters as well, I can simply increase the length of the array.

결국 영문 소문자를 기준으로 배열을 만들고, a를 기준으로 각 영소문자의 수를 세어 넣었다.

그리고 두번째 문자열에서 반복문을 돌면서 카운트를 하나씩 줄이도록 하니 시간 효율이 확실히 개선되었다.

이 문제에서는 영소문자만 나온다고 해서 별다른 처리는 안했지만, 다른 문자들까지 커버하고 싶다면 배열 길이를 늘리면 될 듯하다.