2416. 문자열의 접두사 점수 합계
난이도:어려움
주제: 배열, 문자열, Trie, 계산
비어있지 않은 문자열로 구성된 크기 n의 배열 단어가 제공됩니다.
문자열 단어의 점수를 문자열 단어의 수로 정의합니다. 즉, 단어는 단어[i]의 접두사입니다.
크기 n의 배열 답변을 반환합니다. 여기서 답변[i]는 단어[i]의 모든 비어 있지 않은 접두사 점수의 합계입니다.
참고 문자열은 그 자체의 접두사로 간주됩니다.
예 1:
예 2:
제약조건:
힌트:
해결책:
접두사 작업에 특히 효율적인 Trie 데이터 구조를 사용할 수 있습니다. Trie의 각 노드는 단어의 문자를 나타내며 각 노드에 카운터를 유지하여 해당 접두사가 발생한 횟수를 저장합니다. 이를 통해 해당 접두어로 시작하는 단어 수를 계산하여 각 접두사의 점수를 효율적으로 계산할 수 있습니다.
Trie에 단어 삽입:
접두사 점수 계산:
응답 배열 구축:
이 솔루션을 PHP로 구현해 보겠습니다: 2416. 문자열의 접두사 점수 합계
<?php class TrieNode { /** * @var array */ public $children; /** * @var int */ public $count; public function __construct() { $this->children = []; $this->count = 0; } } class Trie { /** * @var TrieNode */ private $root; public function __construct() { $this->root = new TrieNode(); } /** * Insert a word into the Trie and update the prefix counts * * @param $word * @return void */ public function insert($word) { ... ... ... /** * go to ./solution.php */ } /** * Get the sum of prefix scores for a given word * * @param $word * @return int */ public function getPrefixScores($word) { ... ... ... /** * go to ./solution.php */ } } /** * @param String[] $words * @return Integer[] */ function sumOfPrefixScores($words) { ... ... ... /** * go to ./solution.php */ } // Example usage: $words1 = ["abc", "ab", "bc", "b"]; $words2 = ["abcd"]; print_r(sumOfPrefixScores($words1)); // Output: [5, 4, 3, 2] print_r(sumOfPrefixScores($words2)); // Output: [4] ?> <h3> 설명: </h3> <ol> <li> <p><strong>TrieNode 클래스:</strong></p> <ul> <li>각 노드에는 하위 배열(단어의 다음 문자를 나타냄)과 이 접두사를 공유하는 단어 수를 추적하는 개수가 있습니다.</li> </ul> </li> <li> <p><strong>트라이 클래스:</strong></p> <ul> <li>insert 메소드는 Trie에 단어를 추가합니다. 각 문자를 삽입하면 각 노드의 개수가 증가하여 이 접두사가 붙은 단어 수를 나타냅니다.</li> <li>getPrefixScores 메소드는 특정 단어의 모든 접두사에 대한 점수 합계를 계산합니다. Trie를 통과하여 단어의 문자에 해당하는 각 노드의 수를 합산합니다.</li> </ul> </li> <li> <p><strong>주요 기능(sumOfPrefixScores):</strong></p> <ul> <li>First, we insert all words into the Trie.</li> <li>Then, for each word, we calculate the sum of scores for its prefixes by querying the Trie and store the result in the result array.</li> </ul> </li> </ol> <h3> Example: </h3> <p>For words = ["abc", "ab", "bc", "b"], the output will be:<br> </p> <pre class="brush:php;toolbar:false">Array ( [0] => 5 [1] => 4 [2] => 3 [3] => 2 )
This approach ensures that we efficiently compute the prefix scores in linear time relative to the total number of characters in all words.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
위 내용은 문자열의 접두사 점수 합계의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!