[Leetcode/C++] 242_Valid Anagram

문제 링크: https://leetcode.com/problems/valid-anagram/

문제는 다음과 같습니다.
보자마자 s, t를 정렬 후 이 둘을 비교해서 같으면 true를 반환, 다르면 false를 반환해야겠다는 생각을 했습니다.

처음 제가 푼 풀이는 다음과 같습니다.

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        
        int res = 1;
        int i, j;
        
        for(i=0, j=0; i<s.size(), j<t.size(); i++, j++){
            if(s[i]!=t[j]){
                res = 0;
                break;
            }
        }
        
        if(res==0 || i!=s.size() || j!=t.size()) return false;
        else return true;
    }
};

그리고 주의해야 할 점은 입력받은 두 문자열의 길이가 다른 경우도 모두 고려해야한다는 것이었습니다!
그래서 마지막 if문에서 i, j의 값도 모두 확인해주었습니다.

문제를 풀고난 후 생각해보니,
그냥 정렬된 두 문자열이 같은지 다른지만 판별하면 되더라구요?

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        
        return s==t;
    }
};

바로 이 풀이입니다.

다른 풀이도 참고해보았는데요, 정렬 말고도 해쉬맵(Hashmap)을 쓰기도 하더라구요 ㅎㅎ
저도 그래서 c++ stl unordered_map을 이용하여 풀어보았습니다.

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size()!=t.size()) return false;
        
        unordered_map<char, int> um;
        
        for(int i=0; i<s.size(); i++){
            um[s[i]]++;
        }
        for(int i=0; i<t.size(); i++){
            um[t[i]]--;
            if(um[t[i]]<0){
                return false;
            }
        }
        return true;
    }
};

오 일단 속도가 엄청 빨라졌습니다.
정렬에서는 nlogn이었는데, 해쉬맵에서는 n이니까 많이 향상된 것 같아요!

다른분께서 푼 풀이도 한 번 참고하겠습니다.

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s==t) return true;
        if (s.size()!=t.size()) return false;
        unordered_map <char, int> umap;
        for (int i=0; i<s.size(); i++) {
            umap[s[i]]++;
            umap[t[i]]--;
        }
        for (auto it: umap) {
            if (it.second) return false;
        }
        return true;
    }
};

[링크] https://leetcode.com/problems/valid-anagram/discuss/971245/C%2B%2B-or-Sort-Hashmap-Array-or-Time%3A-O-(nlogn)-greater-O-(n)-Space%3A-O-(n)-greater-O-(1)