Problem
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.
Example
Given s = "SodhanaLibrary", dict = ["Sodhana", "Library"].
Return true because "SodhanaLibrary" can be segmented as "Sodhana Library".
JavaScript Code
function wordBreak(s, dict) { var t = []; for(var i=0; i<=s.length; i++){ t[i] = false; } t[0] = true; //set first to be true, why? //Because we need initial state console.log(t); for(var i=0; i<s.length; i++){ //should continue from match position if(!t[i]) continue; for(var a in dict){ var len = dict[a].length; var end = i + len; if(end > s.length) continue; if(t[end]) continue; if(s.substring(i, end) == dict[a]){ t[end] = true; } } console.log(t); } return t[s.length]; } var s = "sodhanalibrary"; var dict = ["sodhana", "library"]; console.log(wordBreak(s,dict));
0 comments:
Post a comment