Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. 

For example, given s = "leetcode", dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Intuitive backtracking approach got Time Limits Exceed.

DP: use a binary array to describe whether the first part of the string is in the dict. For each non-zero element in the array, update the elements by checking the second part of the string.

Comments

Post a Comment

Popular posts from this blog

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.  Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police. class Solution { public: int rob(vector &num) { if (num.size() < 1) return 0; vector result; result.push_back(num[0]); for (int i = 1; i < num.size(); ++i) { int curr_max = 0; for (int j = 0; j < i - 1; ++j) { curr_max = max(curr_max, num[i] + result[j]); } curr_max = max(curr_max, result[i - 1]); curr_max = max(curr_max, num[i]); result.p...
Read more

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.  Try to solve it in linear time/space.  Return 0 if the array contains less than 2 elements. You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range. In order to solve this in linear time, we cannot use general sorting algorithm. Here we use bucket sort. First, we scan the array to find the min and the max values.   We can then create n - 1 buckets with equal size. Suppose we have n elements in total, then we have n - 2 elements except the min and the max. Scan the array again to put the n - 2 elements into these buckets. We should have at least one empty bucket. For each bucket, we record the min and the max for all the elements within that bucket.  Finally, we scan all the buckets, and maintain the maximum gap. Note that the maximum gap between the successive elements in the sorted...
Read more

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.   The path may start and end at any node in the tree. Solution: For root node, first check two subtrees and figure out the path with maximum sum in each subtree (and the path must contains the root node). More precisely, we can compare root->val, root->val + leftsubtree, root->val + rightsubtree. But this is not enough since the maximum path might contains two subtrees. We have to compute the value of root->val + leftsubtree + rightsubtree as well. The problem is, we cannot directly return this value since this path cannot go to upper nodes anymore. So we also use another global variable to store the maximum sum in each recursion, and update this variable once we find any path with larger sum. The following code passes the LeetCode Online Large Judge. Thanks for the useful comments.
Read more