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

给定一个字符串和一个词典dict，确定s是否可以根据词典中的词分成

一个或多个单词。

比如，给定

s = “leetcode”

dict = [“leet”, “code”]

返回true，因为"leetcode"可以被分成"leet code"

• 解析

经过分析题目，状态为F(i)：前i个字符能否被分割；

举例来分析：给定一个字符串s=“1234567890”，dic = [“12”,“34”,“56”,“78”,“90”]

前一个字符能否被分割：F(1)：“1” ，false不能被分割。

前两个字符能否被分割：F(2): “12”，前两个字符可以被看成F(1)和“2”，而F(1)在上一步就证实已经不能被分割，所以“1”，“2”的方案失败；但是如果我们给状态初始化为F(0) = “ ”，一个空字符并且定义他可以被分割，那么用F(0)&&dict.contains(s.substring(“12”)),F(0)为真，而字符串“12”也可以被找到，所以为真。

经过初始化后，判断前三个字符串能否被分割：F(3): “123”；F(1)&&任何都是失败，而F(2)&&“3”，因为“3”找不到所以失败，而F(3)：“123”也找不到所以也失败。

判断前四个字符串能否被分割：F(4)：“1234”；“1”和“234”的方案找不到所以失败；“12”&&dict.contains(s.substring(“34”))F(2)是真的，而“34”可以被找到，所以F(4)为true。

依次类推。。。。

所以状态递推公式为F(i) = F(j)&&dict.contains(s.substring(j,i));

代码：

import java.util.Set;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        if(dict.size() == 0 && s.length() == 0 && s == null){
            return false;
        }
        int len = s.length();
        boolean[] cut = new boolean[len+1];
        //初始化
        cut[0] = true;
        for(int i = 1;i <= len; i++){
            //F(i) = F(j)&& dict.find(s(j+1,i))
            for(int j = 0;j<i;j++){
                if(cut[j] && dict.contains(s.substring(j,i))){
                    cut[i] = true;
                    break;
                }
            }
        }
        return cut[len];
    }
}