-
LeetCode 140: Word Break II
link Backtrack If a prefix s[0:l] is a dictionary word, we then try breaking s[l:]. Time: , space (disregarding output-size): . The solutions can be thought of as paths in a DAG. If we can construct the DAG, we can traverse the paths and collect the sentences. Dynamic Programming Subproblem Say the input string is…
-
LeetCode 1143: Longest Common Subsequence
link Dynamic Programming Subproblem Say input strings are and . Let be the length of the longest common subsequence between the pair of prefixes and . is the solution. Order Subproblems on a -grid and row-wise processing gives a topological ordering. Time: , space: . A subproblem depends on the subproblems that are on the…
-
LeetCode 1842: Next Palindrome Using Same Digits
link Since num is a palindrome, if there is a center, it cannot be rearranged because the center is the only digit having odd count. We can rearrange the digits in one of the two halves only because, the other half would be mirror-image. So, we rearrange left half. If the digits were sorted in…
-
LeetCode 647: Palindromic Substrings
link We can check if a string is a palindrome in two ways: Both ways take time. However, there is a difference: the count of possible pairs of end points is whereas the count of possible centers is . Process inwards from two ends Brute force Try all possible substrings. Time: , space: . Dynamic…
-
LeetCode 139: Word Break
link Note, word = “” + word is a valid segmentation as long as word is in wordDict. Dynamic programming Subproblem Let denote if the prefix can be broken into words. Then: Note, we assume an empty string can be segmented. Order Edges go from smaller ‘s to a bigger . Processing in the order…
-
LeetCode 39: Combination Sum
link Backtracking For each element , we take instances of it such that and try to make using other elements. We process candidates in a sorted order to be able to use a set to keep only unique combinations. Recursion tree has height and width . So, time: , space: . Dynamic programming Subproblem Let…
-
LeetCode 152: Maximum Product Subarray
link Brute force Take max of all possible subarrays. Products of all possible subarrays starting at a particular index can be computed in time. Since there are possible starting indices, total time: , space: . Dynamic programming Subproblem Without negative numbers Let be the largest product in nums[0:i+1] for a subarray that includes nums[i]. Then,…
-
LeetCode 213: House Robber II
link Dynamic Programming Sub-problem Say Rob(i) is the maximum money achievable by robbing the houses in nums[0…i]. Then: . Order The directed graph is cyclic. To break the cycle, we do two passes. First pass robs first house and thus skips the last house. Second pass skips first house. We take the maximum of these…
-
LeetCode 542: 01 Matrix
link Dynamic programming For a one-cell (i, j) we can reach the nearest zero-cell via one of its four neighbors. So, if the four neighbors of the cell have already been solved, we can solve (i, j). This suggests DP. Sub-problem Order The directed graph has cycles between neighbors. We can process black arrows in…
-
LeetCode 338: Counting Bits
link Inspect binary representation Count 1’s in binary representation for each index. For a number , count_ones take time. So, the time taken to count ones for all the numbers is the sum: or time is . We use Sterling’s approximation: . So, . Time: , extra space (disregarding output): . Dynamic programming On every…
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
unreasonably effective 