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:O(n*n)
public class Solution { public boolean wordBreak(String s, Set<String> dict){ if (s==null || dict==null){ return false; } if (dict.size()==0) return s.length()==0; boolean[] DP=new boolean[s.length()+1]; 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; break; } } } return DP[s.length()]; } }
沒有留言:
張貼留言