Leo-20180916.md

Leo Lei | 雷雨

Sep 09, 2018

1. Leetcode

Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "abcdefg", wordDict = ["abc", "de", "fg", "d", "efg]
Output: true
Explanation: Return true because "abcdefg" can be segmented as "abc de fg"
or "abc d efg".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Analysis

The brute force solution would be breaking the input into parts and checking if every part can be found in wordDict. There are 2ⁿ ways to cut the input, the time complexity would be O(2ⁿ). -- See implementation 1 for the code

It's easy to see that there are lots of overlapped sub-problems. For example, s[i:j] could be a sub-array of s[m:n] or s[x:y], so s[i:j] could be touched twice, which is a waste of time. Therefore, we can memorize the output of the sub-problems for future use(a.k.a. memoization).

Implementation

Solution 1: Brute Force

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        wordDict = set(wordDict)
        def _helper(s):
            if s in wordDict:
                return True
            for i in range(len(s)):
            # seg s into two parts, return True if both parts are breakable
                if _helper(s[:i]) and _helper(s[i:]):
                    return True
            return False
        return _helper(s)

Solution 2: Recursion with memoization

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        wordDict = set(wordDict)
        memo = dict(zip(wordDict, [True]*len(wordDict)))
        def _helper(s):
            if s in memo:
                return memo[s]
            for i in range(len(s)):
                if _helper(s[:i]) and _helper(s[i:]):
                    memo[s] = True
                    return True
            memo[s] = False
            return False
        return _helper(s)

2. Article and comment

Google Developer: Inside look at modern web browser (part 2) TBC

3. New skill/tool

TBC

4. Share an article

TBC