242. Valid Anagram

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

Valid Anagram - LeetCode

난이도 : easy

문제

t가 s의 애너그램인지를 판별하라

 

두가지로 풀이 했다.

1. s와 t 를 정렬을 해서 같은이 아닌지 판단한다. 이때 시간복잡도는 최소 O(NlogN) 이다.

제약사항에서 문자열의 최대 길이는 5 * 10^4

• 1 <= s.length, t.length <= 5 * 10^4

2. map 을이용하여 문자를 삽입하고 s 의 입력은 ++ 카운트 t 의 입력인 -- 카운트를 한다. map 에 원소를 순회하면서 value 의 값이 0 이 아니면 아나그램이 아닌 것으로 판정한다.

 

코드

정렬 후 비교

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

 

map 을 활용하여 키 값으로 판정

class Solution {
public:
    bool isAnagram(string s, string t) {
        // 문자열이 길이다 다르면 anagram 이 아니다.
        if (s.length() != t.length()) return false;
        map<char, int> m;
        
        for(int i = 0; i < s.size(); ++i) {
            m[s[i]]++; // first 1
            m[t[i]]--; // second 0
        }
        
        for(auto a:m) {
            if(a.second) return false;
        }
        return true;
    }
};