솔루션: 유효한 아나그램

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 드셨거나 유용하셨다면 이 게시물에 좋아요를 누르거나 추천my solution post on Leetcode's forums 해주세요.

Leetcode 문제 #242(쉬움): 유효한 아나그램

설명:

두 개의 문자열 s 및 t 가 주어지면 t 가 s 의 아나그램인지 확인하는 함수를 작성하십시오.


예:


예 1:



입력:
s = "아나그램", t = "나가람"

산출:
진실



예 2:



입력:
s = "쥐", t = "자동차"

산출:
거짓



제약 조건:

문자열에 소문자 알파벳만 포함되어 있다고 가정할 수 있습니다.

아이디어:

단어의 아나그램은 기본적으로 동일한 문자를 동일한 빈도로 사용하는 다른 단어입니다. 우리는 문자와 그 빈도에만 관심이 있으므로 빈도 맵을 사용하는 것이 쉬운 선택입니다.

우리는 소문자를 다루기 때문에 더 전통적인 Map 대신 Array를 사용하고 저장을 위해 문자를 유니코드 번호(97 - 122)로 변환하여 이 기능을 더 효율적으로 만들 수 있습니다.

먼저 첫 번째 문자열 S를 반복하고 주파수 맵(fmap)에서 각 문자 코드 위치를 증가시킵니다. 그런 다음 두 번째 문자열 T를 실행하고 fmap에서 문자 코드 위치를 감소시킵니다. 0 아래로 내려가면 T에 S와 같지 않은 문자 빈도가 있다는 것을 알고 있으므로 false를 반환해야 합니다.

하지만 문제 없이 끝까지 간다면 true를 반환해야 합니다.


구현:

자바스크립트에서는 형식화된 배열 Int16Array를 사용하여 프로세스의 성능을 더욱 높일 수 있습니다.

파이썬에는 이 문제를 더욱 빠르게 만드는 문자열 함수 count()가 있습니다.


자바스크립트 코드:

var isAnagram = function(S, T) {
    let len = S.length, fMap = new Int16Array(123)
    if (T.length !== len) return false
    for (let i = 0; i < len; i++)
        fMap[S.charCodeAt(i)]++
    for (let i = 0; i < len; i++)
        if (--fMap[T.charCodeAt(i)] < 0) return false
    return true
};

파이썬 코드:

class Solution:
    def isAnagram(self, S: str, T: str) -> bool:
        SMap = {c: S.count(c) for c in set(S)}
        TMap = {c: T.count(c) for c in set(T)}
        return SMap == TMap

자바 코드:

class Solution {
    public boolean isAnagram(String S, String T) {
        int len = S.length();
        int[] fMap = new int[123];
        if (T.length() != len) return false;
        for (int i = 0; i < len; i++)
            fMap[S.codePointAt(i)]++;
        for (int i = 0; i < len; i++)
            if (--fMap[T.codePointAt(i)] < 0) return false;
        return true;
    }
}

C++ 코드:

class Solution {
public:
    bool isAnagram(string S, string T) {
        int len = S.length();
        int fMap [123] = {0};
        if (T.length() != len) return false;
        for (int i = 0; i < len; i++)
            fMap[int(S[i])]++;
        for (int i = 0; i < len; i++)
            if (fMap[int(T[i])]-- == 0) return false;
        return true;
    }
};