LC139 - Word Break

Problem

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example

Sample 1

Input: s = "leetcode", wordDict = ["leet","code"]

Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

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

Solution

Dynamic Programming

Break into the subproblem of segmenting substrings into a sequence of words. Time complexity of this solution is $O(n^2)$ while space complexity is $O(s)$ due to the use of an array that is the length of the string.

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
	arr = [False] * (len(s) + 1)
	# base case is always True, empty string always can be segmented
	arr[0] = True

	for i in range(1, len(s) + 1):
		# true if any is true
		for j in range(i):
			if arr[j] and s[j:i] in wordDict:
				arr[i] = True
				break
	return arr[-1]