문자열의 접두사 점수 합계

2416. 문자열의 접두사 점수 합계

난이도:어려움

주제: 배열, 문자열, Trie, 계산

비어있지 않은 문자열로 구성된 크기 n의 배열 단어가 제공됩니다.

문자열 단어의 점수를 문자열 단어의 수로 정의합니다. 즉, 단어는 단어[i]의 접두사입니다.

• 예를 들어 단어 = ["a", "ab", "abc", "cab"]인 경우 "ab"는 "ab"와 "ab"의 접두사이므로 "ab"의 점수는 2입니다. "abc".

크기 n의 배열 답변을 반환합니다. 여기서 답변[i]는 단어[i]의 모든 비어 있지 않은 접두사 점수의 합계입니다.

참고 문자열은 그 자체의 접두사로 간주됩니다.

예 1:

• 입력: 단어 = ["abc","ab","bc","b"]
• 출력: [5,4,3,2]
• 설명: 각 문자열에 대한 답은 다음과 같습니다.
  • "abc"에는 "a", "ab", "abc"라는 3개의 접두사가 있습니다.
  • 접두사 "a"가 붙은 문자열 2개, 접두사 "ab"가 붙은 문자열 2개, 접두사 "abc"가 붙은 문자열 1개가 있습니다.
  • 합계는 답[0] = 2 + 2 + 1 = 5입니다.
  • "ab"에는 "a"와 "ab"라는 2개의 접두사가 있습니다.
  • 접두사 "a"가 붙은 문자열 2개, 접두사 "ab"가 붙은 문자열 2개가 있습니다.
  • 합계는 답[1] = 2 + 2 = 4입니다.
  • "bc"에는 "b"와 "bc"라는 2개의 접두사가 있습니다.
  • 접두사 "b"가 붙은 문자열 2개, 접두사 "bc"가 붙은 문자열 1개가 있습니다.
  • 합계는 답[2] = 2 + 1 = 3입니다.
  • "b"에는 "b"라는 접두사가 1개 있습니다.
  • 접두사 "b"가 붙은 문자열이 2개 있습니다.
  • 합계는 답[3] = 2입니다.

예 2:

• 입력: 단어 = ["abcd"]
• 출력: [4]
• 설명:
  • "abcd"에는 "a", "ab", "abc", "abcd"라는 4개의 접두사가 있습니다.
  • 각 접두어의 점수는 1이므로 총합은 답[0] = 1 + 1 + 1 + 1 = 4입니다.

제약조건:

• 1
• 1
• word[i]는 영문 소문자로 구성됩니다.

힌트:

1. 각 접두사의 점수를 효율적으로 추적할 수 있는 데이터 구조는 무엇입니까?
2. 트라이를 사용하세요. 여기에 모든 단어를 삽입하고 각 접두사를 몇 번이나 방문했는지 알려주는 카운터를 각 노드에 유지하세요.

해결책:

접두사 작업에 특히 효율적인 Trie 데이터 구조를 사용할 수 있습니다. Trie의 각 노드는 단어의 문자를 나타내며 각 노드에 카운터를 유지하여 해당 접두사가 발생한 횟수를 저장합니다. 이를 통해 해당 접두어로 시작하는 단어 수를 계산하여 각 접두사의 점수를 효율적으로 계산할 수 있습니다.

접근하다:

1. Trie에 단어 삽입:

   • Trie 문자에 각 단어를 문자별로 삽입해 보겠습니다.
   • 각 노드(문자를 나타냄)에서 해당 접두사를 통과하는 단어 수를 추적하는 카운터를 유지 관리합니다.

2. 접두사 점수 계산:

   • 각 단어에 대해 Trie에서 접두사를 탐색하면서 각 노드에 저장된 카운터를 합산하여 각 접두사에 대한 점수를 계산합니다.

3. 응답 배열 구축:

   • 각 단어에 대해 모든 접두사의 점수 합계를 계산하여 결과 배열에 저장합니다.

이 솔루션을 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]
?>

설명:

1. TrieNode 클래스:

   • 각 노드에는 하위 배열(단어의 다음 문자를 나타냄)과 이 접두사를 공유하는 단어 수를 추적하는 개수가 있습니다.

2. 트라이 클래스:

   • insert 메소드는 Trie에 단어를 추가합니다. 각 문자를 삽입하면 각 노드의 개수가 증가하여 이 접두사가 붙은 단어 수를 나타냅니다.
   • getPrefixScores 메소드는 특정 단어의 모든 접두사에 대한 점수 합계를 계산합니다. Trie를 통과하여 단어의 문자에 해당하는 각 노드의 수를 합산합니다.

3. 주요 기능(sumOfPrefixScores):

   • First, we insert all words into the Trie.
   • 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.

Example:

For words = ["abc", "ab", "bc", "b"], the output will be:

Array
(
    [0] => 5
    [1] => 4
    [2] => 3
    [3] => 2
)

• "abc" has 3 prefixes: "a" (2 words), "ab" (2 words), "abc" (1 word) -> total = 5.
• "ab" has 2 prefixes: "a" (2 words), "ab" (2 words) -> total = 4.
• "bc" has 2 prefixes: "b" (2 words), "bc" (1 word) -> total = 3.
• "b" has 1 prefix: "b" (2 words) -> total = 2.

Time Complexity:

• Trie Construction: O(n * m) where n is the number of words and m is the average length of the words.
• Prefix Score Calculation: O(n * m) as we traverse each word's prefix in the Trie.

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:

• LinkedIn
• GitHub

위 내용은 문자열의 접두사 점수 합계의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!