单词切分.md

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".

---

给定一个字符串s和一个词典，判断s是否可以被切割成一个或者多个词典中的单词。

比如，给定s="leetcode"，dict=["leet","code"]，应该返回true，因为"leetcode"可以被切分成"leet"和"code"两个片段。

解题思路

使用动态规划，假设$f(j)$的真值表示$s[0,j]$是否可以被分词，则： $f(n)=f(i)&&f(i+1,n)$ 那么如果我们要求$f(n)$是否可以被分词，我们首先需要求出$f(i)$，然后再对$s[i+1,n]$的字符串判断是否可以分词，要求$f(i)$，又要让$j$从0开始到$i-1$，判断$f(j)$为真且$f(j，i)$为真…

伪代码如下：

假设s的长度为length，使用array[length+1]代表f(i)到f（n）的真值，则：
初始array[0]=true：
for i in 0 to length:
		for j in 0 to i:
				if array[j]&&dict.contains(s[j:i]):
						array[i]=true;
return array[length]

代码

这里