\section{Word Break} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given

s = \code{"leetcode"},

dict = \code{["leet", "code"]}.

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

\subsubsection{Solution}

\begin{Code}

public boolean wordBreak(String s, List<String> wordDict) {

int n = s.length();

boolean[] dp = new boolean[n + 1];

dp[0] = true;

for (int i = 1; i <= s.length(); i++) {

for (String word : wordDict) {

int j = i - word.length();

if (j >= 0 && dp[j] && s.substring(j, i).equals(word)) {

dp[i] = true;

break;

}

}

}

return dp[n];

}

\end{Code}

This is XeTeX, Version 3.14159265-2.6-0.99996 (TeX Live 2016) (preloaded format=xelatex 2017.9.4) 7 SEP 2017 20:04

[14] [15] [16] [17] [18] [19] [20]

<use "images/8-queens.png" > [21] [22]

[23] [24] [25] [26]

[27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39]

Underfull \hbox (badness 3118) in paragraph at lines 1808--1809

[40] [41]

<use "images/watch.jpg" > [42] [43] [44] [45] [46] [47] [48]

[49] [50] [51] [52] [53]

<use "images/unlock.png" > [54] [55])

592704 words of memory out of 5000000

Output written on leetcode-backtracking.pdf (57 pages).