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"
.
public class Solution { public boolean wordBreak(String s, Set<String> dict) { // Note: The Solution object is instantiated only once and is reused by each test case. if(dict == null||s.length() == 0) return false; boolean[] dp = new boolean[s.length()+1];//remeber add one dp[0] = true; for(int i = 1 ; i <= s.length();i++){ for(int k =0; k <i ; k++){ if(dp[k]&&dict.contains(s.substring(k,i))) dp[i] = true; } } return dp[s.length()]; } }
mistakes: 1) in i loop, the biggest value is s.length() 2)when build new dp make array.length = s.length() +1; in case of "[]"