The intuition for this solution is tricky but not impossible. I'm sure many had the same question as me: "Why does dp[ len(s) ] = 1 ???" Here is the order of thinking you must take to understand: 1. The problem can be broken up into subproblems - When you draw out the decision tree, repeated work becomes apparent. Really draw it out for yourself. Draw out the trees for the following strings: "2121", "121", "21", "1". From this, you can understand dp[i] = dp[i+1] + dp[i+2] 2. Consider the edge case of an empty string " ". It does not have a leading 0, so it can validly be decoded into an empty string " " (no letter representations). 3. Consider the edge case of a single character string "1". Intuitively, we know that there is only 1 way to decode it. But how does that fit within our dp[i] = dp[i+1] + dp[i+2] formula? IT DOESN'T! But in drawing the trees, our intuition tells us that the formula should work. How can we make it work for a string with len(s) = 1? We must include it in our base case. The execution would go like this: START i. dfs(0) ii. dfs(1) -> since i == len(s), we return dp[len(s)] which we have set to equal 1 iii. The if-clause containing dfs(i+2) won't be executed, because ( i + 1 < len(s) ) won't be satisfied. iv. We return the result, which only equals dfs(1) at this point, which is 1 END 4. You see, you cannot intuitively come up with dp [ len(s) ] = 1 because you must come up with it when considering this edge case in order to force our formula to work.
Been a while since I was an interviewee, but now if someone asked me to invert a binary tree I would politely suggest that they simply invert their traversal on read, as this would have the same effect while negating the expensive, recursive memory swapping exercise. If they really wanted to see how I would do it (to demonstrate understanding of certain concepts) I'd call out their career management bumbledom and show myself out. Man's ain't got time for silly games.
The explanation is very good. However the test case have changed over the past 3 year. If i run this code in (c++) I get a "runtime error: signed integer overflow" for the input of "nums = [0,10,10,10,10,10,10,10,10,10,-10,10,10,10,10,10,10,10,10,10,0]".
just hope you don't have a number to encode at the end of your string, encoding an address for example like this is bound to have issue. You could use invisible characters or better combinaison of characters (like #a trigram of the software / your name / the company#). Remember that this type of problem you have to ask question to define what are the constraint and type of data, and explain why you would implement this and not something else.
if you have the coords of all fresh oranges and of all the rotten oranges, at the start, can't you just do a A* (?) pathfinder algo from each good orange to each rotten orange, get - per good oragen - the shortest of them if multiple, if you can find such path for each fresh orange, the answer is the longest 'short path to a rotten one', else the answer is -1 aka : you can just do this massively in parallel and the moment you find even just 1 good orange with no solution in the A*pathfinding to a rotten orange, you can answer -1, not caring when which other orange turns rotten or not. done with the graph of 4:45 : A-D : rows, 1-4, colums, rotten are at A1 and A4, good ones at B1,B2,B3,B4, C3,C4 and D1 listing resuls to each rotten one : in (path to rotten at A1, path to rotten at A4): BA(1,4), B2(2,3), B3(3,2), B4(4,1), C3(4,3), C4(5,2), D1(None) -> 1 with none -> insta "-1" answer if the good one in D1 wasn't there: remove the longer pathways: B1: 1, B2: 2, B3:2, B4:1, C3:3, C4:2: highest number is 3 -> 3 is the answer. the "how long does it take to get rotten as well" part takes the longstest time and can all be done parallele for all good-bad-combo's. the path will have to be horizontal or vertical over other good oranges of course, not over empty spots.
to optimise even further: if for any good orange the response is 1 step, no need to test the paths to other rotten oranges 'cause none will be shorter, if there were, it would be a rotten orange from the start and not a good one.
I was asked to do this without extra space, I like this explanation ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-EHpS2TBfWQg.html&ab_channel=VivekanandKhyade-AlgorithmEveryDay
How about encoding each string to base64 (that has no commas, for example) and using comma to separate, then using Split method (C#), then decoding all? That was my solution to it, and in my case looked really simple. IDK about the big O complexity though.
inverting a binary tree here is just a function that swaps elements. so the technique is just swap from outer to inner or something. You can also use index calculation if you want to use other method.
I've always thought inverting binary tree is different from what I'm thinking. But this example is just some sort of swapping. Is that what inverting a binary tree means?
the string "4total" would have your code try to read 64 characters when it turns it into "64total" which is why you need a character so it becomes 6#4total
Yo I just search for this and you made a vid about it. For those who didn't know what this algorithm called -> Hare-Tortoise algorithm And lots of video explain how it works.
