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 text “ilikemobile” is breakable into [“i”,”like”,”mobile”] text “ilikesamobile” is breakable into [“ili”,”kesa”,”mobile”] text “ilikesammobile” is […]
Tag Archives: dp
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 – Given a […]
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. Let’s […]
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]. First of all, lets solve the problem with less constraint. Suppose we need to find out […]
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)). LCS can be solved by DP in O(n^2) 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 For example, longest palindromic substring of S = “babaabca” is “baab”. In a previous post I described a simple O(n^2) time solution for this problem. But there is a very beautiful […]
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 For example, longest palindromic substring of S = “babaabca” is “baab”. In a previous post I described a simple O(n^2) time solution for this problem. But there is a very beautiful […]
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 […]