[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

 

애너그램? 한  단어나 문구의 글자를 재배열해서 다른 뜻을 가진 단어, 문구를 만드는것

모든 문자의 종료랑 개수가 일치하는지 확인해야함

 

접근 방법: 

길이 검사를해서 길이가 다르면 false를 반환

문자 빈도수 배열: 소문자만 있다는 제약조건을 활용해서 26크기의 배열을 사용 출현 빈도를 계산한다

빈도수를 비교해서 두 문자열의 문자 빈도수가 일치하는지를 확인한다.

 

 

수도코드

function isAnagram(s,t);
	if length(s) != length(t);
    	return false
        //26개 알파벳소문자에 대한 빈도수 배열 생성
        frequenct = array of 26 zeros
        
        //첫번째 문자열의 문자 빈도수 증가
        for each character c in s:
        index =c-'a'
        frequency[index]++
        
        //두번째 문자열의 문자 빈도수 감소
        for each character c in t:
        	index=c-'a'
            frequecy[index]--
            
            //음수가 된다면 t에는 있지만 s에는 없는 문자가 있따
            if frequency[index]<0;
            return false
            
            //모든 빈도수가 0이면 애너그림
            return true

 

문제 발생:

빈도수를 비교할때 문자열을 앞에서부터 카운트 하면서 빈도수를 저장하는것은 이해가 되는데

// 3. 첫 번째 문자열(s)의 각 문자 빈도수 증가
for (int i = 0; i < s.length(); i++) {
    charCount[s.charAt(i) - 'a']++;
}

 

두번째 문자열의 각 문자에 대해 카운터를 감소하는거 이해가 잘 안됨

카운터가 음수가 되면 같은 문자가 아니라는 의미라는데..

 

해결:

첫번째 문자열에서 각 글자를 담은 주머니를 만들고, 두번째 문자열을 읽으면서 해당 글자를 하나씩 빼는것인데

주머니에 없는 글자를 빼려고 하면 - 가 되면서 애너그램이 아니게 되는것이다.