dev/democards/problems/problems/1639.number-of-ways-to-form-a-target-string-given-a-dictionary.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "You are given a list of strings of the **same length** `words` and a string\n",
    "`target`.\n",
    "\n",
    "Your task is to form `target` using the given `words` under the following\n",
    "rules:\n",
    "\n",
    "  * `target` should be formed from left to right.\n",
    "  * To form the `ith` character ( **0-indexed** ) of `target`, you can choose the `kth` character of the `jth` string in `words` if `target[i] = words[j][k]`.\n",
    "  * Once you use the `kth` character of the `jth` string of `words`, you **can no longer** use the `xth` character of any string in `words` where `x <= k`. In other words, all characters to the left of or at index `k` become unusuable for every string.\n",
    "  * Repeat the process until you form the string `target`.\n",
    "\n",
    "**Notice**  that you can use **multiple characters** from the **same string**\n",
    "in `words` provided the conditions above are met.\n",
    "\n",
    "Return _the number of ways to form`target` from `words`_. Since the answer may\n",
    "be too large, return it **modulo** `109 + 7`.\n",
    "\n",
    "\n",
    "\n",
    "**Example 1:**\n",
    "\n",
    "\n",
    "\n",
    "    Input: words = [\"acca\",\"bbbb\",\"caca\"], target = \"aba\"\n",
    "    Output: 6\n",
    "    Explanation: There are 6 ways to form target.\n",
    "    \"aba\" -> index 0 (\" _a_ cca\"), index 1 (\"b _b_ bb\"), index 3 (\"cac _a_ \")\n",
    "    \"aba\" -> index 0 (\" _a_ cca\"), index 2 (\"bb _b_ b\"), index 3 (\"cac _a_ \")\n",
    "    \"aba\" -> index 0 (\" _a_ cca\"), index 1 (\"b _b_ bb\"), index 3 (\"acc _a_ \")\n",
    "    \"aba\" -> index 0 (\" _a_ cca\"), index 2 (\"bb _b_ b\"), index 3 (\"acc _a_ \")\n",
    "    \"aba\" -> index 1 (\"c _a_ ca\"), index 2 (\"bb _b_ b\"), index 3 (\"acc _a_ \")\n",
    "    \"aba\" -> index 1 (\"c _a_ ca\"), index 2 (\"bb _b_ b\"), index 3 (\"cac _a_ \")\n",
    "\n",
    "\n",
    "**Example 2:**\n",
    "\n",
    "\n",
    "\n",
    "    Input: words = [\"abba\",\"baab\"], target = \"bab\"\n",
    "    Output: 4\n",
    "    Explanation: There are 4 ways to form target.\n",
    "    \"bab\" -> index 0 (\" _b_ aab\"), index 1 (\"b _a_ ab\"), index 2 (\"ab _b_ a\")\n",
    "    \"bab\" -> index 0 (\" _b_ aab\"), index 1 (\"b _a_ ab\"), index 3 (\"baa _b_ \")\n",
    "    \"bab\" -> index 0 (\" _b_ aab\"), index 2 (\"ba _a_ b\"), index 3 (\"baa _b_ \")\n",
    "    \"bab\" -> index 1 (\"a _b_ ba\"), index 2 (\"ba _a_ b\"), index 3 (\"baa _b_ \")\n",
    "\n",
    "\n",
    "**Example 3:**\n",
    "\n",
    "\n",
    "\n",
    "    Input: words = [\"abcd\"], target = \"abcd\"\n",
    "    Output: 1\n",
    "\n",
    "\n",
    "**Example 4:**\n",
    "\n",
    "\n",
    "\n",
    "    Input: words = [\"abab\",\"baba\",\"abba\",\"baab\"], target = \"abba\"\n",
    "    Output: 16\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**Constraints:**\n",
    "\n",
    "  * `1 <= words.length <= 1000`\n",
    "  * `1 <= words[i].length <= 1000`\n",
    "  * All strings in `words` have the same length.\n",
    "  * `1 <= target.length <= 1000`\n",
    "  * `words[i]` and `target` contain only lowercase English letters."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "num_ways (generic function with 1 method)"
     },
     "metadata": {},
     "execution_count": 1
    }
   ],
   "cell_type": "code",
   "source": [
    "# @lc code=start\n",
    "using LeetCode\n",
    "\n",
    "function num_ways(word::Vector{String}, target::String)\n",
    "    len_t, len_s, len_w = length(target), length(word[1]), length(word)\n",
    "    dp, cntr = fill(0, len_t, len_s), fill(0, len_s, 128)\n",
    "\n",
    "    for i in 1:len_s\n",
    "        for s in word\n",
    "            cntr[i, s[i] |> Int] += 1\n",
    "        end\n",
    "    end\n",
    "    for i in 1:len_s-len_t+1\n",
    "        dp[1, i] = cntr[i, target[1] |> Int]\n",
    "    end\n",
    "    for i in 2:len_t\n",
    "        acc = 0\n",
    "        for j in i:i+len_s-len_t\n",
    "            mul = cntr[j, target[i] |> Int]\n",
    "            acc += dp[i - 1, j - 1]\n",
    "            dp[i, j] = acc * mul % 1000000007\n",
    "        end\n",
    "    end\n",
    "    # display(dp)\n",
    "    sum(dp[len_t, len_t:end]) % 1000000007\n",
    "end\n",
    "# @lc code=end"
   ],
   "metadata": {},
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
   ],
   "metadata": {}
  }
 ],
 "nbformat_minor": 3,
 "metadata": {
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.1"
  },
  "kernelspec": {
   "name": "julia-1.10",
   "display_name": "Julia 1.10.1",
   "language": "julia"
  }
 },
 "nbformat": 4
}