adamk.org

This problem solution relies on binary exponentiation. The key insight is that
2^10 = 2^5 * 2^5
2^5 = 2^2 * 2^2 * 2
So we can base our solution on recursively solving pow(x, n/2) and multiplying it by itself to get our result. If n is odd then we have to do an extra multiplication of x. Base case is n == 0, which results in 1. Be careful not to repeatedly call the recursive function twice as that will result in O(n) time. For O(log n) time we remember the result of pow(x, n/2) and then multiply it by itself once recursion has unravelled.

A few fiddly edge cases like dealing with negative exponents, where we can just return 1.0 / pow(x, -n). The most tricky edge case is INT_MIN, which would overflow if we negate it. So instead I add one to the exponent, deal with that and then multiply it by the remaining x.

There is also an iterative solution but I find that less intuitive. Here are my whiteboard notes for the iterative solution:

And here is the c++ source code is here:
https://gist.github.com/adamkorg/2982fd48ba21a3b364b123de963cb902

Use a hash map with key being the sorted word and value being a vector of strings of all instances of that anagram. Iterate through input array, filling the hash map. Then iterate through the hash map adding the map values (vectors) to our result vector.

The idea with my solution is that you work your way through layers of the box, starting with the outside layer and then moving inwards. For each layer we step through four points at a time, starting at the corners and then working our way around to other points on the edges. On the whiteboard I have highlighted the order with colours. I find it easiest to figure out the outermost layer first and then modify the logic to handle layer offsets.

The obvious way to solve this is to repeatedly call next_permutation() from the standard library. Another way to solve it is to implement what next_permutation() does and I have done that in a previous solution:
https://www.adamk.org/leetcode-31-next-permutation/

Here is my recursive solution with backtracking. The nums parameter is the pool of numbers to choose from and the sel parameter is the current selection. We start with nums full and as we recurse we will get to a state where nums is empty and sel is full and at that point we add sel to our result set.

Here is the source code for the next_permutation based solution:
https://gist.github.com/adamkorg/1d306abeb41eede8ff0dab43e1569d25
And here is the code for the recursive solution:

A more efficient solution is https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ although this does not generate outputs in lexicographical order.

The obvious solution is to use a recursive function. If we find a wildcard then we recurse every position in s from that point onwards. The problem with this is that it is very slow if there are a lot of wildcards and some of the leetcode test cases will fail. So we need to add DP memoization to eliminate duplicate branches of recursive calls.

I also have a different solution that was inspired by this post:
http://yucoding.blogspot.com/2013/02/leetcode-question-123-wildcard-matching.html

The solution basically steps through matches and then if it finds a * wildcard pattern character then it stores its positions in the pattern and string. It then attempts to just step past the wildcard and if at some point it fails then it rewinds back to the original position but skips forward one position in the string. So it tests out further matches by using an increasing number of characters used by the wildcard.

Here are my whiteboard notes where I try to explain the logic. Note that I use the cs and cp variables as the indexes of the current positions in the pattern and string. However at the top of the whiteboard I started out using “is” and “ip” instead of cs and cp. I also use sp for the star position in the pattern and ss for the position of the star matching in the string.

I think this has a worst case time complexity of O(n²). I think it might be possible to use the KMP algorithm to achieve O(n) but that is quite a bit more complicated. I think this solution is far more elegant. Here is the c++ source code:

The general steps to do long multiplication are fairly straightforward but the implementation was a bit fiddly. I think it would be easier to to reverse the strings and work on them in reverse, then the least significant index will be zero. It is a bit fiddly to do the other way, which is how I did it below:

And the c++ source code:
https://gist.github.com/adamkorg/1d83d0f6eb273b2545e745196c8924d1

Here is a slightly simpler solution, where I add the numbers in reverse: