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 =
dict =
s =
"leetcode"
,dict =
["leet", "code"]
.
Return true because
"leetcode"
can be segmented as "leet code"
.Solution:
Using dynamic programmingpublic class Solution { public boolean wordBreak(String s, Set<String> dict) { boolean[] segmented = new boolean[s.length()+1]; segmented[0] = true; for(int i=0; i<s.length(); i++) { for (int j=i; j>=0; j--) { if(segmented[j] && dict.contains(s.substring(j,i+1))) { segmented[i+1] = true; break; } } } return segmented[s.length()]; } }
No comments :
Post a Comment