Number of Ways to Form a Target String Given a Dictionary - LeetCode 1639 - Python Solution

Показать описание

Solution Blog: (sign into leetcode to view)

First! We build a lookup array where the ith index maps to the ith column. At every cell we will store the number of occurences every letter appears at that ith column.

Next! We create our recursive call, cache it with @cache and pass in i to indicate the current index of the target letter we're try to build & c the current column we're considering.

Two Base Cases!!
We run out of letters in our target --- return 1, this is a valid path!
We run out of columns --- return 0, we weren't able to construct our target

Two recursive Calls!!
Skip the current column, move on to the next!
Use the number of paths we can go down at the current column, and iterate to the next call and next target letter!

I hope my code helps a little - have an awesome day!

Code with Carter

Рекомендации по теме

Комментарии

Hey man, great job on the video! Just a thought, you might want to look into removing the echo with free AI software to make ur vids even better. One of the ones I've heard about is called Descript and their Studio Sound feature

juanfernandez

it was so satisfying getting this problem right, it took me one TLE to come up with the lookup table idea. also, why do you use @cache instead of a 2d dp[i][c] where you save the result? is there ever a difference?

brady

Number of Ways to Form a Target String Given a Dictionary - LeetCode 1639 - Python Solution

Number of Ways to Form a Target String Given a Dictionary | Leetcode 1639

Number of Ways to Form a Target String Given a Dictionary - Leetcode 1639 - Python

LeetCode 1639. Number of Ways to Form a Target String Given a Dictionary

Number of Ways to Form a Target String Given a Dictionary - LeetCode 1639 - Python Solution

1639. Number of Ways to Form a Target String Given a Dictionary (Leetcode Hard)

Number of Ways to Form a Target String Given a Dictionary | Recur | Memo | Leetcode 1639 | MIK

Number of Ways to Form a Target String Given a Dictionary | Bottom Up | Leetcode 1639 | MIK

1639. Number of Ways to Form a Target String Given a Dictionary | LeetCode Daily Challenge | POTD

1639. (Hard) Number of Ways to Form a Target String Given a Dictionary - Daily Leetcode (Day 75)

Permutations and Combinations | Finding the number of ways to form an eight-digit number divisible b

Number of Ways to Form a Target String Given a Dictionary - Leetcode 1639 - Python

1639. Number of Ways to Form a Target String Given a Dictionary || Dynamic Programming

Eat Eggs This Way: The Secret to Eliminating Stroke Risks, Preventing Memory Loss!

Array : Number of ways to form array using only 3 elements?

Leetcode 1639. Number of Ways to Form a Target String Given a Dictionary || Java Solution

Leetcode 1639. Number of Ways to Form a Target String Given a Dictionary (multi-dimentional dp)

Writing Numbers Using the Standard Form | Ways to Write Numbers Lesson 1/6 | MathHelpTutor.com

Number of ways you can form pairs with a group of people when certain people cannot be paired...

3 Ways to Write a Number : Expanded Form, Written form, and Standard Form

Leetcode 1639. Number of Ways to Form a Target String Given a Dictionary

Number of Ways to Form a Target String Given a Dictionary | Leetcode | Programming in Tamil | C++

Counting ways when a person can form pair with at most one using dynamic programming

Leetcode 1639. Number of Ways to Form a Target String Given a Dictionary

Writing Numbers Using the Expanded Form | Ways to Write Numbers Lesson 2/6 | MathHelpTutor.com