• 28.9%

https://leetcode.com/problems/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.

UPDATE (2017/1/4):

The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

https://discuss.leetcode.com/topic/7299/c-dynamic-programming-simple-and-fast-solution-4ms-with-optimization

6ms, September 9, 2016

C++ Dynamic Programming simple and fast solution (4ms) with optimization

We use a boolean vector dp[]. dp[i] is set to true if a valid word (word sequence) ends there. The optimization is to look from current position i back and only substring and do dictionary look up in case the preceding position j with dp[j] == true is found.

https://discuss.leetcode.com/topic/2545/a-solution-using-bfs

A solution using BFS

People have posted elegant solutions using DP. The solution I post below using BFS is no better than those. Just to share some new thoughts.

We can use a graph to represent the possible solutions. The vertices of the graph are simply the positions of the first characters of the words and each edge actually represents a word. For example, the input string is “nightmare”, there are two ways to break it, “night mare” and “nightmare”. The graph would be

0–>5–>9

| _^

The question is simply to check if there is a path from 0 to 9. The most efficient way is traversing the graph using BFS with the help of a queue and a hash set. The hash set is used to keep track of the visited nodes to avoid repeating the same work.

For this problem, the time complexity is O(n^2) and space complexity is O(n), the same with DP. This idea can be used to solve the problem word break II. We can simple construct the graph using BFS, save it into a map and then find all the paths using DFS.

#### python

https://discuss.leetcode.com/topic/8109/simple-dp-solution-in-python-with-description

Simple DP solution in Python with description

75ms, 18.48%, September 7, 2016

The idea is the following:

• d is an array that contains booleans
• d[i] is True if there is a word in the dictionary that ends at ith index of s AND d is also True at the beginning of the word

Example:

• s = “leetcode”
• words = [“leet”, “code”]
• d[3] is True because there is “leet” in the dictionary that ends at 3rd index of “leetcode”
• d[7] is True because there is “code” in the dictionary that ends at the 7th index of “leetcode” AND d[3] is True

The result is the last index of d.

https://discuss.leetcode.com/topic/16701/4-lines-in-python

4 lines in Python

ok[i] tells whether s[:i] can be built.

#### java

https://discuss.leetcode.com/topic/6156/java-implementation-using-dp-in-two-ways

12ms, September 9, 2016

Java implementation using DP in two ways

https://discuss.leetcode.com/topic/9615/dfs-with-path-memorizing-java-solution

DFS with Path Memorizing Java Solution

I write this method by what I learned from @mahdy in his post Decode Ways

Use a set to record all position that cannot find a match in dict. That cuts down the run time of DFS to O(n^2)