{"id":5824,"date":"2019-11-09T23:08:12","date_gmt":"2019-11-10T07:08:12","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5824"},"modified":"2019-11-13T02:06:53","modified_gmt":"2019-11-13T10:06:53","slug":"leetcode-1255-maximum-score-words-formed-by-letters","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1255-maximum-score-words-formed-by-letters\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1255. Maximum Score Words Formed by Letters"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1252 1253 1254 1255 Weekly Contest 162  - \u5237\u9898\u627e\u5de5\u4f5c\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/1XMpzhFUvco?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>Given a list of&nbsp;<code>words<\/code>, list of&nbsp; single&nbsp;<code>letters<\/code>&nbsp;(might be repeating)&nbsp;and&nbsp;<code>score<\/code>&nbsp;of every character.<\/p>\n\n\n\n<p>Return the maximum score of&nbsp;<strong>any<\/strong>&nbsp;valid set of words formed by using the given letters (<code>words[i]<\/code>&nbsp;cannot be used two&nbsp;or more times).<\/p>\n\n\n\n<p>It is not necessary to use all characters in&nbsp;<code>letters<\/code>&nbsp;and each letter can only be used once. Score of letters&nbsp;<code>'a'<\/code>,&nbsp;<code>'b'<\/code>,&nbsp;<code>'c'<\/code>, &#8230; ,<code>'z'<\/code>&nbsp;is given by&nbsp;<code>score[0]<\/code>,&nbsp;<code>score[1]<\/code>, &#8230; ,&nbsp;<code>score[25]<\/code>&nbsp;respectively.<\/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 = [\"dog\",\"cat\",\"dad\",\"good\"], letters = [\"a\",\"a\",\"c\",\"d\",\"d\",\"d\",\"g\",\"o\",\"o\"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]\n<strong>Output:<\/strong> 23\n<strong>Explanation:<\/strong>\nScore  a=1, c=9, d=5, g=3, o=2\nGiven letters, we can form the words \"dad\" (5+1+5) and \"good\" (3+2+2+5) with a score of 23.\nWords \"dad\" and \"dog\" only get a score of 21.<\/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 = [\"xxxz\",\"ax\",\"bx\",\"cx\"], letters = [\"z\",\"a\",\"b\",\"c\",\"x\",\"x\",\"x\"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]\n<strong>Output:<\/strong> 27\n<strong>Explanation:<\/strong>\nScore  a=4, b=4, c=4, x=5, z=10\nGiven letters, we can form the words \"ax\" (4+5), \"bx\" (4+5) and \"cx\" (4+5) with a score of 27.\nWord \"xxxz\" only get a score of 25.<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> words = [\"leetcode\"], letters = [\"l\",\"e\",\"t\",\"c\",\"o\",\"d\"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong>\nLetter \"e\" can only be used once.<\/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;= 14<\/code><\/li><li><code>1 &lt;= words[i].length &lt;= 15<\/code><\/li><li><code>1 &lt;= letters.length &lt;= 100<\/code><\/li><li><code>letters[i].length == 1<\/code><\/li><li><code>score.length ==&nbsp;26<\/code><\/li><li><code>0 &lt;= score[i] &lt;= 10<\/code><\/li><li><code>words[i]<\/code>,&nbsp;<code>letters[i]<\/code>&nbsp;contains only lower case English letters.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Combination<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(2^n)<br>Space complexity: O(n)<\/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\nclass Solution {\npublic:\n  int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {\n    vector<int> counts(26);\n    vector<int> scores(words.size());\n    for (char c : letters) ++counts[c - 'a'];\n    for (int i = 0; i < words.size(); ++i)       \n      for (char c : words[i]) scores[i] += score[c - 'a'];\n    int ans = 0;\n    function<void(int, int)> dfs = [&](int s, int cur) {\n      if (cur > ans) ans = cur;\n      for (int i = s; i < words.size(); ++i) {\n        bool valid = true;\n        for (char c : words[i]) valid &#038;= --counts[c - 'a'] >= 0;\n        if (valid) dfs(i + 1, cur + scores[i]);\n        for (char c : words[i]) ++counts[c - 'a'];        \n      }\n    };\n    dfs(0, 0);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a list of&nbsp;words, list of&nbsp; single&nbsp;letters&nbsp;(might be repeating)&nbsp;and&nbsp;score&nbsp;of every character. Return the maximum score of&nbsp;any&nbsp;valid set of words formed by using the given letters&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[122,42],"class_list":["post-5824","post","type-post","status-publish","format-standard","hentry","category-searching","tag-combination","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5824","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=5824"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5824\/revisions"}],"predecessor-version":[{"id":5827,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5824\/revisions\/5827"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5824"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5824"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5824"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}