This problem is also known as the Levenshtein distance. It is possible to solve recursively but that is very inefficient. Here is how to do it with dynamic programming. My initial logic didn’t work with recurring characters. I’ve highlighted the fix in red.
Source for the above:
https://gist.github.com/adamkorg/38fa5934e9aeec0565d2f1dd50b73c3e
And here’s code for a variation with my current coding style tastes:
My original solution (whiteboard notes below) involved manually parsing the directory names by stepping over characters one by one looking for the slash character. This was somewhat fiddly and error prone and required some fixes after trying the test cases. I reimplemented using std::getline() and stringstream to do the tokenising, which proved simpler and less error prone. See gist source code for that implementation below.
Here’s the source code for that initial solution:
https://gist.github.com/adamkorg/36adeab8156778d3852c37a57fb250aa
And here’s the source code for the simplified getline()/stringstream solution:
I went down some time consuming dead ends on this problem. I focused on combinations and binomial coefficients. But these suffered from number variable overflow. What I initially missed was that the results of each n follows a fibonacci sequence. It is easy once you realise that.
Use binary search to solve this problem. Start with left as 1 and right as x. Then find the mid point and test by squaring it. If mid * mid is equal to x then we have our answer. If the mid*mid is smaller than x then we need to lower our search, so we reduce our search range by looking between left and mid. If the square was bigger than x then we search between mid and right. We repeat this until we find an exact match or our left and right pointers overlap. If they overlap then mid is slightly too big and we need to return mid-1. There are a few edge cases to consider:
Just be careful about integer overflow. One of the test cases has x as close to INT_MAX, which would cause integer overflow in our initial mid*mid calculation. I overcome this by checking against a limit for mid (46340, which is the square root of INT_MAX) so that the square cannot exceed the integer limit. I noticed on leetcode that most solutions use a long variable to calculate the square, which on Unix systems (LP64) will work but not on Windows (LLP64).
I quite liked this problem even though it seems to have a lot downvotes. It takes a while to solve because there is quite a lot of logic to encode but it is very doable. For me it was important to plan out the complicated case of the variable length spacing of multiple words on non-last lines. I thought through how to calculate these spaces by defining a bunch of dependant variables.
Similar to the previous problem (Leetcode 66 – Plus One). Loop around both input strings from last char to first char. Add each digit and remember carries if needed.
Source code for above solution:
https://gist.github.com/adamkorg/7f7cc67a39fe8198ccdf1974c4eb7961
And below is code for a slightly more concise solution:
Straightforward. Just add one to the rightmost number and then perform a carry to next significant digits if necessary.
This is not a great leetcode question because it is not clearly defined. This would be fine as a real interview question where you can work out the requirements by asking the interviewer questions but in leetcode you just have to use trial and error by submitting to see if it passes the test cases. So the following cases need to pass: “.1” -> true and “2.” -> true. Also the exponent number can have an optional sign character (+/-).
This is a variation of the the two previous problems (Unique Paths). So we just use dynamic programming to calculate running costs at each cell in the grid. We add the current grid cell cost to the lesser value of the running costs in the cells to the left and up. In the recursive solution be aware that we need to use return INT_MAX rather than 0 if the cell is out of bounds.
Source code for solutions:
Recursive with DP memoization
Iterative DP with O(n²) auxiliary space
Iterative DP with O(n) auxiliary space
Iterative DP with O(1) auxiliary space by modifying grid param
This is fairly similar to the previous problem “Leetcode 62: Unique Paths” but here we will set the memo cell value to zero if there is an obstacle in that cell, as there is no route to the finish from that cell. There is a weird leetcode test case that causes integer overflow if int is used in the memo vector. Changing the DP memo to use long instead of int resolves the problem.
Here is the source code for my various solutions:
Recursive with DP memo
Iterative DP, O(n²) time and space
Iterative DP with O(n) space optimisation
