-
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: Given such a DAG, the overall approach is as follows: Observations Explicit DAG Shortest paths Given a DAG with positive edge weights and a source node, we want to find shortest path distances to every other node…
-
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): A digit is available for the empty cell (row, col) only if none of the above three contains the digit. If there…
-
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: Time , space: .
-
LeetCode 151: Reverse Words in a String
link Time: , space: . We can do the reversing in-place: Since Python’s str is immutable, we first convert s to a List[str] and once reversing is done, return s[0:n] as a str. Time: , space: .
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
unreasonably effective 