Recursion

Let’s solve LeetCode problem 55: Jump Game. The instructions are as follows: You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise. Constraints: 1 <= nums.length <= 10^4 0 <= nums[i] <= 10^5 I solved this in two ways: a less efficient approach using dynamic programming, and a very fast greedy method. Let’s dive in! ...

Today, let’s look at LeetCode problem 216: Combination Sum III. The instructions are as follows: Find all valid combinations of \(k\) numbers that sum up to \(n\) such that the following conditions are true: Only numbers 1 through 9 are used. Each number is used at most once. Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order. ...

In this post, we’ll be solving LeetCode problem 1143. We have two strings text1 and text2 with sizes \(n\) and \(m\), respectively. We want to find the length of their longest common subsequence (LCS). A subsequence of a string s is obtained by deleting zero or more characters from s. Strategy Let’s assume we have two strings: s1 with size n1 and s2 with size n2. Let’s also assume we know their LCS length. What can we say about LCS length when we append a character c1 to s1 and a character c2 to s2? ...

A trie is data structure which holds strings. It allows fast search and insertion of strings, as well as fast search of string prefixes. This can be especially useful for text autocompletion and spellcheck. In this post, we implement a trie in C++ with three basic operations: search, insert, and startsWith. This is the solution to LeetCode 208. The problem assumes that all words use characters a-z in the English alphabet, but our solution can be extended to include more characters. ...