-
LeetCode 416: Partition Equal Subset Sum
link Assigning the positive numbers in two equal-sum subsets is same as creating one set having sum equal to half of the total sum. We can use Dynamic Programming. This is like coin-change except a number cannot be reused. Sub-problem Let solutions[ (i, s) ] represent the sub-problem of creating a subset with target sum…
-
LeetCode 1137: N-th Tribonacci Number
link We can use Dynamic Programming. Sub-problem solutions[i] = solutions[i-1] + solutions[i-2] + solutions[i-3] Trivial sub-problems: solutions[0], solutions[1], and solutions[2] Order Since solutions[i] only depends on solutions[j] where j < i, we can process the sub-problems in increasing order of i and that would be a topologically sorted order.
-
LeetCode 322: Coin Change
link We can use Dynamic Programming. Sub-problem Say solutions[amount] represents the minimum number of coins required to change that amount. A sub-problem, solutions[amount-coin], may not be solvable and to represent that case we initialize solutions with except solutions[0] which has trivial solution 0. Order Since solutions[amount] depends on the solutions[amount-coin] and coin is positive, if…
-
Dynamic Programming
Approach As long as the below two conditions hold, we can use Dynamic Programming to solve a problem: Sub-problem: We can formulate the solution to the original problem as a function of the solutions to “smaller” versions or sub-problems. The “smallest” sub-problems are trivially solved. Node: One node represents one sub-problem. Edge: There is an…
-
LeetCode 473: Matchsticks to Square
link Adding up the matchsticks gives the square’s and the square’s expected side length is . Now, using all the matchsticks exactly once, we need to build the four sides–each side must have the expected length. Backtracking From a side’s point of view We try making one side at a time using all combinations of…
-
LeetCode 37: Sudoku Solver
link We collect all empty cells in a list and try filling them up using only the currently available digits for that cell. As a pre-processing step, we also populate (and later use): One set per row to record which digits have already been used in that row. One set per col to record which…
-
LeetCode 2193: Minimum Number of Moves to Make Palindrome
link Similarly to how we validate if a string is a palindrome, we turn the string into a palindrome starting with the two ends and converging towards the center. If the two ends do not match, we change one end into another, taking the cheaper of the two available options. Time: , space: .
-
LeetCode 246: Strobogrammatic Number
link Two ends must form a Strobogrammatic pair and if there is a center it must be Strobogrammatic. Time: , space: .
-
LeetCode 408: Valid Word Abbreviation
link Non-numeric portion of abbr must match char-by-char with word. For numeric portion: No leading zeros. Remaining length of word must be big enough to skip over. Time , space: .
-
LeetCode 151: Reverse Words in a String
link Time: , space: . We can do the reversing in-place: First pass: Copy the words to the beginning of s and remove extra spaces. Now the words are in s[0:n] Second pass: Reverse the entire string (s[0:n]) Third pass: Restore each individual word by reversing Since Python’s str is immutable, we first convert s…
-
Subscribe
Subscribed
Have a WordPress.com account? Log in now.
