1915. Number of Wonderful Substrings

문제링크

설명

#

문자열 중에 최대 한 글자만 홀수 번 나타나면 완벽한 문자열임 단어 word가 주어졌을때, 여기에서 나타날 수 있는 모든 완벽한 문자열의 수를 구하셈 (world는 a~j만으로 구성)

풀이

#

1. 단어를 순회하면서, 해당 단어를 비트로 바꿔 bitmask 집합에 넣는다. 이 비트마스를 key로 하는 dict에서, dict[key] 가 존재한다면, 그만큼 더한다 dict[key]를 1증가시킨다

왜? XOR연산은, 같은 숫자가 짝수번 연산되면 모두 상쇄되어 사라진다. 비트마스크는 현재의 상태 를 의미하는데, 이전에 똑같은 마스크가 존재했다는 뜻은, 그 사이에 있는 모든 단어들은 짝수번 등장한다는 뜻이다 근데 왜 dict[key]만큼 더함??

우리가 단어를 순회하면서 구하는것은, 현재 문자를 끝으로 하는 완벽한 부분 문자열의 수이다 만약 지금의 비트마스크 전에 n개의 비트마스크가 있다고 가정하면, 그 n개의 비트마스크 모두 부분 문자열의 시작이 될 수 있는 것이다 하지만, 이건 부분문자열의 모든 단어 등장 짝수번 등장하는 경우이다.

2. 빈도가 홀수번 등장하는 단어를 찾는다.

위에서 구했던 모든 단어가 짝수번 등장하는 문자열 에서, 강제로 단어를 넣어 하나의 문자가 홀수번 등장하고, 나머지가 모두 짝수인 문자열 을구한다 위와 같은 원리로, 이 문자열의 상태(bitmask)가 존재한다면 그만큼 더해주면 된다.

전체코드

#

 def wonderfulSubstrings(word: str) -> int:
        bitmask=0
        counter=defaultdict(int)
        counter[0] = 1
        answer=0
        
        for w in word:
            bit =  1<<(ord(w)-97)   
            bitmask ^=bit #현재비트를 토글해서 "상태"를 구함

            answer+=counter[bitmask] #이전에 "현재상태"가 등장한 수만큼 구함(모든단어빈도짝수)
            counter[bitmask] +=1 #현재상태 추가
            
            for i in range(10):
                answer += counter[bitmask ^ 1<<i] # 강제로 단어를 집어넣어서, 하나가 홀수일 경우의 수 구함
                
        return answer

솔직히 어색하고 개어려움 더 최적화한사람들도 있는데 여기까지만 하려고 함 담에 비슷한 문제가 나올때 풀 수 있을지 모르겠음