{"id":7589,"date":"2020-10-31T15:10:07","date_gmt":"2020-10-31T22:10:07","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7589"},"modified":"2020-10-31T15:11:22","modified_gmt":"2020-10-31T22:11:22","slug":"leetcode-1639-number-of-ways-to-form-a-target-string-given-a-dictionary","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1639-number-of-ways-to-form-a-target-string-given-a-dictionary\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1639. Number of Ways to Form a Target String Given a Dictionary"},"content":{"rendered":"\n<p>You are given a list of strings of the&nbsp;<strong>same length<\/strong>&nbsp;<code>words<\/code>&nbsp;and a string&nbsp;<code>target<\/code>.<\/p>\n\n\n\n<p>Your task is to form&nbsp;<code>target<\/code>&nbsp;using the given&nbsp;<code>words<\/code>&nbsp;under the following rules:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>target<\/code>&nbsp;should be formed from left to right.<\/li><li>To form the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;character (<strong>0-indexed<\/strong>) of&nbsp;<code>target<\/code>, you can choose the&nbsp;<code>k<sup>th<\/sup><\/code>&nbsp;character of the&nbsp;<code>j<sup>th<\/sup><\/code>&nbsp;string in&nbsp;<code>words<\/code>&nbsp;if&nbsp;<code>target[i] = words[j][k]<\/code>.<\/li><li>Once you use the&nbsp;<code>k<sup>th<\/sup><\/code>&nbsp;character of the&nbsp;<code>j<sup>th<\/sup><\/code>&nbsp;string of&nbsp;<code>words<\/code>, you&nbsp;<strong>can no longer<\/strong>&nbsp;use the&nbsp;<code>x<sup>th<\/sup><\/code>&nbsp;character of any string in&nbsp;<code>words<\/code>&nbsp;where&nbsp;<code>x &lt;= k<\/code>. In other words, all characters to the left of or at index&nbsp;<code>k<\/code>&nbsp;become unusuable for every string.<\/li><li>Repeat the process until you form the string&nbsp;<code>target<\/code>.<\/li><\/ul>\n\n\n\n<p><strong>Notice<\/strong>&nbsp;that you can use&nbsp;<strong>multiple characters<\/strong>&nbsp;from the&nbsp;<strong>same string<\/strong>&nbsp;in&nbsp;<code>words<\/code>&nbsp;provided the conditions above are met.<\/p>\n\n\n\n<p>Return&nbsp;<em>the number of ways to form&nbsp;<code>target<\/code>&nbsp;from&nbsp;<code>words<\/code><\/em>. Since the answer may be too large, return it&nbsp;<strong>modulo<\/strong>&nbsp;<code>10<sup>9<\/sup>&nbsp;+ 7<\/code>.<\/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 = [\"acca\",\"bbbb\",\"caca\"], target = \"aba\"\n<strong>Output:<\/strong> 6\n<strong>Explanation:<\/strong> There are 6 ways to form target.\n\"aba\" -&gt; index 0 (\"acca\"), index 1 (\"bbbb\"), index 3 (\"caca\")\n\"aba\" -&gt; index 0 (\"acca\"), index 2 (\"bbbb\"), index 3 (\"caca\")\n\"aba\" -&gt; index 0 (\"acca\"), index 1 (\"bbbb\"), index 3 (\"acca\")\n\"aba\" -&gt; index 0 (\"acca\"), index 2 (\"bbbb\"), index 3 (\"acca\")\n\"aba\" -&gt; index 1 (\"caca\"), index 2 (\"bbbb\"), index 3 (\"acca\")\n\"aba\" -&gt; index 1 (\"caca\"), index 2 (\"bbbb\"), index 3 (\"caca\")\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 = [\"abba\",\"baab\"], target = \"bab\"\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> There are 4 ways to form target.\n\"bab\" -&gt; index 0 (\"baab\"), index 1 (\"baab\"), index 2 (\"abba\")\n\"bab\" -&gt; index 0 (\"baab\"), index 1 (\"baab\"), index 3 (\"baab\")\n\"bab\" -&gt; index 0 (\"baab\"), index 2 (\"baab\"), index 3 (\"baab\")\n\"bab\" -&gt; index 1 (\"abba\"), index 2 (\"baab\"), index 3 (\"baab\")\n<\/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 = [\"abcd\"], target = \"abcd\"\n<strong>Output:<\/strong> 1\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> words = [\"abab\",\"baba\",\"abba\",\"baab\"], target = \"abba\"\n<strong>Output:<\/strong> 16\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>All strings in&nbsp;<code>words<\/code>&nbsp;have the same length.<\/li><li><code>1 &lt;= target.length &lt;= 1000<\/code><\/li><li><code>words[i]<\/code>&nbsp;and&nbsp;<code>target<\/code>&nbsp;contain only lowercase English letters.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<p>dp[i][j] := # of ways to form target[0~j] where the j-th letter is from the i-th column of words.<br>count[i][j] := # of words that have word[i] == target[j]<\/p>\n\n\n\n<p>dp[i][j] = dp[i-1][j-1] * count[i][j]<\/p>\n\n\n\n<p>Time complexity: O(mn)<br>Space complexity: O(mn) -&gt; 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++\">\nclass Solution {\npublic:\n  int numWays(vector<string>& words, string target) {\n    constexpr int kMod = 1e9 + 7;\n    const int n = target.length();\n    const int m = words[0].length();\n    \n    vector<long> dp(n); \/\/ dp[j] = # of ways to form t[0~j]\n    for (int i = 0; i < m; ++i) {\n      vector<int> count(26);\n      for (const string& word: words)\n        ++count[word[i] - 'a'];      \n      for (int j = min(i, n - 1); j >= 0; --j)\n        dp[j] = (dp[j] + (j > 0 ? dp[j - 1] : 1) * \n                    count[target[j] - 'a']) % kMod;\n    }\n    return dp[n - 1];\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a list of strings of the&nbsp;same length&nbsp;words&nbsp;and a string&nbsp;target. Your task is to form&nbsp;target&nbsp;using the given&nbsp;words&nbsp;under the following rules: target&nbsp;should be formed&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,366,4],"class_list":["post-7589","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-omn","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7589","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=7589"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7589\/revisions"}],"predecessor-version":[{"id":7591,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7589\/revisions\/7591"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7589"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7589"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7589"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}