{"id":9832,"date":"2022-09-18T12:44:55","date_gmt":"2022-09-18T19:44:55","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9832"},"modified":"2022-09-18T13:33:53","modified_gmt":"2022-09-18T20:33:53","slug":"leetcode-2416-sum-of-prefix-scores-of-strings","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-2416-sum-of-prefix-scores-of-strings\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2416.\u00a0Sum of Prefix Scores of Strings"},"content":{"rendered":"\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 2416. Sum of Prefix Scores of Strings - \u5237\u9898\u627e\u5de5\u4f5c EP402\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/OJ0PMH6M2MQ?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>You are given an array&nbsp;<code>words<\/code>&nbsp;of size&nbsp;<code>n<\/code>&nbsp;consisting of&nbsp;<strong>non-empty<\/strong>&nbsp;strings.<\/p>\n\n\n\n<p>We define the&nbsp;<strong>score<\/strong>&nbsp;of a string&nbsp;<code>word<\/code>&nbsp;as the&nbsp;<strong>number<\/strong>&nbsp;of strings&nbsp;<code>words[i]<\/code>&nbsp;such that&nbsp;<code>word<\/code>&nbsp;is a&nbsp;<strong>prefix<\/strong>&nbsp;of&nbsp;<code>words[i]<\/code>.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, if&nbsp;<code>words = [\"a\", \"ab\", \"abc\", \"cab\"]<\/code>, then the score of&nbsp;<code>\"ab\"<\/code>&nbsp;is&nbsp;<code>2<\/code>, since&nbsp;<code>\"ab\"<\/code>&nbsp;is a prefix of both&nbsp;<code>\"ab\"<\/code>&nbsp;and&nbsp;<code>\"abc\"<\/code>.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>an array&nbsp;<\/em><code>answer<\/code><em>&nbsp;of size&nbsp;<\/em><code>n<\/code><em>&nbsp;where&nbsp;<\/em><code>answer[i]<\/code><em>&nbsp;is the&nbsp;<strong>sum<\/strong>&nbsp;of scores of every&nbsp;<strong>non-empty<\/strong>&nbsp;prefix of&nbsp;<\/em><code>words[i]<\/code>.<\/p>\n\n\n\n<p><strong>Note<\/strong>&nbsp;that a string is considered as a prefix of itself.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> words = [\"abc\",\"ab\",\"bc\",\"b\"]\n<strong>Output:<\/strong> [5,4,3,2]\n<strong>Explanation:<\/strong> The answer for each string is the following:\n- \"abc\" has 3 prefixes: \"a\", \"ab\", and \"abc\".\n- There are 2 strings with the prefix \"a\", 2 strings with the prefix \"ab\", and 1 string with the prefix \"abc\".\nThe total is answer[0] = 2 + 2 + 1 = 5.\n- \"ab\" has 2 prefixes: \"a\" and \"ab\".\n- There are 2 strings with the prefix \"a\", and 2 strings with the prefix \"ab\".\nThe total is answer[1] = 2 + 2 = 4.\n- \"bc\" has 2 prefixes: \"b\" and \"bc\".\n- There are 2 strings with the prefix \"b\", and 1 string with the prefix \"bc\".\nThe total is answer[2] = 2 + 1 = 3.\n- \"b\" has 1 prefix: \"b\".\n- There are 2 strings with the prefix \"b\".\nThe total is answer[3] = 2.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> words = [\"abcd\"]\n<strong>Output:<\/strong> [4]\n<strong>Explanation:<\/strong>\n\"abcd\" has 4 prefixes: \"a\", \"ab\", \"abc\", and \"abcd\".\nEach prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= words.length &lt;= 1000<\/code><\/li><li><code>1 &lt;= words[i].length &lt;= 1000<\/code><\/li><li><code>words[i]<\/code>&nbsp;consists of lowercase English letters.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Trie<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-full\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s1.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s1.png\" alt=\"\" class=\"wp-image-9836\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s2.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s2.png\" alt=\"\" class=\"wp-image-9837\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s3.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s3.png\" alt=\"\" class=\"wp-image-9839\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/09\/lc-2416-ep402-s3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<p>Insert all the words into a tire whose node val is the number of substrings that have the current prefix.<\/p>\n\n\n\n<p>During query time, sum up the values along the prefix path.<\/p>\n\n\n\n<p>Time complexity: O(sum(len(word))<br>Space complexity: O(sum(len(word))<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nstruct Trie {\n  Trie* ch[26] = {};\n  int cnt = 0;\n  void insert(string_view s) {\n    Trie* cur = this;\n    for (char c : s) {\n      if (!cur->ch[c - 'a']) \n        cur->ch[c - 'a'] = new Trie();\n      cur = cur->ch[c - 'a'];\n      ++cur->cnt;\n    }\n  }\n  int query(string_view s) {\n    Trie* cur = this;\n    int ans = 0;\n    for (char c : s) {\n      cur = cur->ch[c - 'a'];\n      ans += cur->cnt;\n    }\n    return ans;\n  }\n};\nclass Solution {\npublic:\n  vector<int> sumPrefixScores(vector<string>& words) {\n    Trie* root = new Trie();\n    for (const string& w : words)\n      root->insert(w);\n    vector<int> ans;\n    for (const string& w : words)\n      ans.push_back(root->query(w));\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an array&nbsp;words&nbsp;of size&nbsp;n&nbsp;consisting of&nbsp;non-empty&nbsp;strings. We define the&nbsp;score&nbsp;of a string&nbsp;word&nbsp;as the&nbsp;number&nbsp;of strings&nbsp;words[i]&nbsp;such that&nbsp;word&nbsp;is a&nbsp;prefix&nbsp;of&nbsp;words[i]. For example, if&nbsp;words = [&#8220;a&#8221;, &#8220;ab&#8221;, &#8220;abc&#8221;, &#8220;cab&#8221;], then&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[217,97,783],"class_list":["post-9832","post","type-post","status-publish","format-standard","hentry","category-tree","tag-hard","tag-prefix","tag-tire","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9832","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9832"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9832\/revisions"}],"predecessor-version":[{"id":9840,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9832\/revisions\/9840"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9832"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9832"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9832"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}