Sunday, May 11, 2014

Leetcode (Python): Word Break

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".

Solution:

Using dynamic programming

class Solution:
    # @param s, a string
    # @param dict, a set of string
    # @return a boolean
    def wordBreak(self, s, dict):
        segmented = [True];
        for i in range (0, len(s)):
            segmented.append(False)
            for j in range(i,-1,-1):
                if segmented[j] and s[j:i+1] in dict:
                    segmented[i+1] = True
                    break
        return segmented[len(s)]

No comments :

Post a Comment