【LeetCode OJ】Word Break

Problem link:

http://oj.leetcode.com/problems/word-break/

We solve this problem using Dynamic Programming method. Let A[0..n-1] be a boolean array, where A[i]=True if and only if s[i..n-1] can be segmented into words. The recursive formula is:

A[i] = True, if s[i..n-1] is a word

A[i] = True, if there exists j > i such that s[i..j-1] is a word and A[j] == True

A[i] = False, otherwise

We fill the A-table from i=n to 0, and return A[0] to tell if s[0..n-1] can be segmented into words.
(Note: there is another way that A[i] means if s[0..i] can be segmented, then the recursive formula becomes a little different, we fill the table from i=0 to n, and return A[n-1])

The pseudo-code is as follows

WORD-BREAK(string s, dictionary d):

  let A[0..n-1] be a new array of False

  for i = n-1 to 0

    if A[i..n-1] is a word in d

      A[i] = True

    else

      for j = i+1 to n-1

        if A[j] == True and s[i..j-1] is a word in d

            A[i] = True

            break

  return A[0]

And the following code is the python solution accepted by OJ.leetcode.

class Solution:

    # @param s, a string

    # @param dict, a set of string

    # @return a boolean

    def wordBreak(self, s, dict):

        """

        We solve this problem using DP

        Define a boolean array A[0..n-1], where

        A[i] = True, means s[i..n-1] can be segmented into words

        ------------------------------------

        The recursive formula is:

        A[i] = True, if there exists j>i (s[i..n-1] = s[i..j-1] + s[j..n-1])

                   such that s[i..j-1] is a word and A[j] = True

        or A[i] = True, if A[i..n-1] is a word

        ------------------------------------

        We fill A-table from i=n-1 to n

        """

        n = len(s)

        A = [False] * n

        i = n-1

        while i >= 0:

            if s[i:n] in dict:

                A[i] = True

            else:

                for j in xrange(i+1, n):

                    if A[j] and s[i:j] in dict:

                        A[i] = True

                        break

            i -= 1

        return A[0]

巴特西

【LeetCode OJ】Word Break

最新文章

热门文章