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:

Blogroll

Follow this blog by Email

Popular Posts