dryear

/**
 * https://leetcode.com/problems/regular-expression-matching/
 *
 * exponential runtime, O(1) space
 *
 * for isMatch(s, p) where both s and p are not empty
 * 1. if p1 is "*"
 *    a) if s0 equals p0, recursively call isMatch(s.substring(1), p) and isMatch(s, p.substring(2))
 *    b) otherwise, recursively call isMatch(s, p.substring(2))
 * 2. if p1 is not "*"

dryear

/**
 * https://leetcode.com/problems/median-of-two-sorted-arrays/
 *
 * O(log (m + n)) runtime, O(1) space
 * where m is the length of the first array, and n is the length of the second array
 *
 * this question can be solved by using the solution of Find the k-th Smallest Element in the Union of Two Sorted Arrays
 *
 * 1. if m + n is odd, the median would be the ((m + n) / 2 + 1)-th smallest element
 * 2. otherwise, the median would be the mean of

dryear

/**
 * https://leetcode.com/problems/counting-bits/
 *
 * O(n) runtime, O(1) space
 *
 * use DP to solve this question
 *
 * assume k is a multiple of two
 * then for k < i < 2k, f(i) = 1 + f(i - k)
 * where f(x) means the number of 1's in x's binary representation

dryear

/**
 * https://leetcode.com/problems/perfect-squares/
 *
 * O(n ^ 1.5) runtime, O(n) space
 *
 * use DP to solve this question
 */

public class Solution {
    public int numSquares(int n) {

dryear

/**
 * https://leetcode.com/problems/word-break-ii/
 *
 * O(n * m) + O(n * num) runtime, O(n) space
 *   where n is the length of the string
 *     m is the length of the longest string in the dictionary
 *     num is the number of solutions
 *
 * use DP and DFS to solve this question with the solution of 139. Word Break
 *

dryear

/**
 * https://leetcode.com/problems/word-break/
 *
 * O(n * m) runtime, O(n) space
 *   where n is the length of the string, and m is the length of the longest string in the dictionary
 *
 * use DP to solve this question
 *
 * 1. state
 *   state[i] means that if the first i characters of the string can be built using strings in the dictionary

dryear

/**
 * https://leetcode.com/problems/partition-equal-subset-sum/
 *
 * O(m * n) runtime, O(m * n) space, where m is the number of elements in the array, and n is the sum of elements
 *
 * this question could become the typical backpack question with proper definition of the state
 *
 * 1. state
 *   state[i][j] means that
 *     if it is possible to find a subset of the set whose members are the first i elements of the array

dryear

/**
 * https://leetcode.com/problems/decode-ways/
 *
 * O(n) runtime, O(1) space
 *
 * this is a typical DP question
 * use a rolling array to get O(1) space
 */

public class Solution {

dryear

/**
 * https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
 *
 * O(n) runtime, O(n) space
 *
 * use the solution for 121. Best Time to Buy and Sell Stock to solve this one
 */

public class Solution {
    public int maxProfit(int[] prices) {

dryear

/**
 * https://leetcode.com/problems/scramble-string/
 *
 * O(n ^ 4) runtime, O(n ^ 3) space, where n is the length of strings
 *
 * use DP to solve this question
 *
 * 1. state
 *   state[i][j][k] means that if s2[j, j+k-1] is a scrambled string of s1[i, i+k-1]
 * 2. function