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

Popular posts from this blog

Maximum Gap

[ITint5] Maximum Subarray for a Circular Array

[CC150] Chapter 8 Object-Oriented Design