Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.
For example, Given a dictionary { i, like, ili, kesa, msun, sam, sung, mobile} then
Tag Archives: dp
Longest palindromic substring in linear time
Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string
Longest palindromic substring in O(n^2) time
Given a string, find the longest substring that is also a palondrom.
One simple solution is to find reverse of S and then find the longest common substring between S and reverse(s). This is also be the longest palindromic substring. That is,
LongestPalindromicSubStr(S) = LCS(S, reverse(S)).
Subset sum problem – Dynamic Programming
Given a set (or multiset) of integers, is there a non-empty subset whose sum is zero?
For example, given the set {−7, −3, −2, 5, 8}, the answer is yes because the subset {−3, −2, 5} sums to zero. The problem is NP-complete. A variant of this problem could be formulated as –
Coin sum problem – Dynamic Programming
Given a value n cents and m type of coins with values { c1, c2, .. , cm} cents each. How many ways can we make the n cents by using the coins as many times as you want?
For example, for n = 5 and C = {1, 2, 5}, there are 4 solutions {{1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {5}}.
Max sum subsequence with non-consecutive elements – Kadane’s Algorithm (DP)
Given an array of integer. Find the maximum sum subsequence such that elements are not consecutive.
For example, A = [−2, 1, −3, 4, −1, 2, 1, −5, 4] then max sum=11 with the subarray [1, 4, 2, 4].
Sliding window min/max – Dynamic Programming
Given an array of integer A[] and the size of sliding window w. Assume that the window of size w starting from left keeps sliding by moving the window one element to right each time. Find the stream of sliding minimums in optimal way. A sliding minimum is the minimum element of current window.