Skip to content

Latest commit

 

History

History
42 lines (27 loc) · 1.27 KB

单词切分.md

File metadata and controls

42 lines (27 loc) · 1.27 KB

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]

代码

这里