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

Analysis

• DP problem
• 状态f[]: 前i个字母能否根据词典中的词被成功分词
• 转化方程：对于每一个i来说，用一个j从0到i之前走一遍，只要遇到j之前的字母可以组成单词，j到i之间的字母可以组成单词，那么f[i]就标记为true并且跳出j循环。
• 初始化：f[0]=true;
• 返回：f[s.length()]

Code

public class Solution{
    public boolean wordBreak(String s, Set<String> dict){
        boolean[] f = new boolean[s.length()+1];
        f[0]=true;
        for(int i=1; i<=s.length(); i++){
            for (int j=0; j<i; j++){
                if(f[j] && dict.contains(s.substring(j,i))){
                    f[i]=true;
                    break;
                }
            }
        }
        return f[s.length()];
    }
}