leetCode

题意：给定一个单词和一个单词序列，看看这个单词能不能分割成一系列单词，并且分割后的单词都在单词序列当中

解法：很简单的dp，用s[0...word.length]表示到第几位能否分割。若word.substring(0,i+1)在这个单词里或者s[j]=true并且word.substring(j+1,i+1)在这个单词序列里，则s[i]=true。最后返回的值为s[word.length-1]

代码如下：

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