2416. Sum of Prefix Scores of Strings

Problem : https://leetcode.com/problems/find-the-length-of-the-longest-common-prefix

 

Difficulty : Hard

 

Status : Solved

 

Time : 00:16:41

 

---

 

문제 설명

비어있지 않은 문자열로 구성된 n 크기의 words 배열을 입력으로 받는다.

우리는 word 문자열에 대한 점수를 word 문자가 words[i]의 접두사를 만족하는 words[i]의 개수로 정의한다.

 

* 예를 들어, words = ["a", "ab", "abc", "cab"]라면 "ab"의 점수는 2이다. "ab"는 "ab"와 "abc"의 접두사이기 때문이다.

 

크기가 n인 answer 배열을 반환하라. 이 때 answer[i]는 words[i]의 모든 비어있지 않은 접두사의 점수의 합이다.

 

문자열은 그 자신에 대한 접두사임에 유의하라.

---

 

풀이

 

트라이 특집. 주어진 words로 트라이를 구성하되, 방문 횟수를 같이 기록하도록 하자. 어떤 노드를 방문할 때마다, 그 노드의 방문 횟수가 1씩 증가하는 구조이다.

 

이제 다시 한번 words를 가지고 방문할 것이다. 이 때, 방문 경로에 있는 모든 방문 횟수의 합이 우리가 구하고자 하는 answer[i]값이 된다. 구체적으로는...

 

• 트라이의 루트에서 현재 위치까지의 문자열은 우리가 탐색하는 word의 접두사를 만족한다.
• 이 때, 방문횟수는 이 문자열이 접두사를 만족하는 모든 문자의 개수가 된다.
• 따라서 word를 방문할 때까지, 모든 방문횟수를 세어주기만 해도 성립된다.

이 문제 역시 이전 문제처럼 해쉬로도 풀 수 있지 않을까 싶다(파이썬의 딕셔너리는 위대하다). 그건 이 글을 읽고 있는 여러분께의 숙제(?) 로 남기도록 한다.

 

 

풀이 코드

class Trie:
    def __init__(self) :
        self.visit = 0
        self.child = dict()
    def isin(self, s:str):
        return s in self.child
    def makeChild(self, s: str):
        self.child[s] = Trie()
    def visitChild(self, s: str, search:bool = False) :
        if not search :
            self.child[s].visit += 1
        return self.child[s]

class Solution:
    def makeTrie(self, word: str) :
        cur = self.trie
        for s in word :
            if not cur.isin(s) :
                cur.makeChild(s)
            cur = cur.visitChild(s)

    def searchTrie(self, word: str) -> int :
        result = 0
        cur = self.trie
        for s in word :
            cur = cur.visitChild(s, True)
            result += cur.visit
        return result

    def sumPrefixScores(self, words: List[str]) -> List[int]:
        self.trie = Trie()
        result = []
        for word in words :
            self.makeTrie(word)
        for word in words :
            result.append(self.searchTrie(word))
        return result