We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Just thinking through the problem, I realized it's just a sideways Pascal's Triangle. Let's say our word is "ABCDE".
A B C
B C D
C D E
Let's look at each individual spot and how many paths there are to them. The "C" in the top right and bottom left have only one path to them, and the same can be said of the "B"s and "A". So, we can write the grid like:
1 1 1
1 C D
1 D E
Now, looking at the remaining "C", there are two ways to reach it. You can either come in from above, or come in from the left. There is only one way to come in from the top and one way to come in from the left, we can say that there are two ways to reach it:
1 1 1
1 2 D
1 D F
Now, for the right-most D, we can see that there are two ways to come in from the left, and one way to come in from above:
1 1 1
1 2 3
1 D E
Following a similar process for the last two letters, we can map out the number of paths to each spot in the matrix as:
1 1 1
1 2 3
1 3 6
Giving us a final answer of 6.
This pattern should look familiar. It is actually a Pascal's Triangle in a different orientation. With a much larger matrix, we would get (sorry for terrible formatting):
1 1 1 1 1 1
1 2 3 4 5 6
1 3 6 10 15 21
1 4 10 20 35 46
1 5 15 35 70 116
1 6 21 46 116 232
For a Pascal's Triangle, one can simply use a Combination function to find the value for any point in the triangle.
I haven't solved it yet, but for those completely clueless about where to even start, hopefully this helps.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Matrix Tracing
You are viewing a single comment's thread. Return to all comments →
Just thinking through the problem, I realized it's just a sideways Pascal's Triangle. Let's say our word is "ABCDE".
Let's look at each individual spot and how many paths there are to them. The "C" in the top right and bottom left have only one path to them, and the same can be said of the "B"s and "A". So, we can write the grid like:
Now, looking at the remaining "C", there are two ways to reach it. You can either come in from above, or come in from the left. There is only one way to come in from the top and one way to come in from the left, we can say that there are two ways to reach it:
Now, for the right-most D, we can see that there are two ways to come in from the left, and one way to come in from above:
Following a similar process for the last two letters, we can map out the number of paths to each spot in the matrix as:
Giving us a final answer of 6.
This pattern should look familiar. It is actually a Pascal's Triangle in a different orientation. With a much larger matrix, we would get (sorry for terrible formatting):
For a Pascal's Triangle, one can simply use a Combination function to find the value for any point in the triangle.
I haven't solved it yet, but for those completely clueless about where to even start, hopefully this helps.