Word Break

[[Dynamic Programming Primer]]

Problem

So, the problem is this: you are given a string s and a dictionary of strings wordDict. Your task is to write a function that returns true if s can be segmented into a space-separated sequence of one or more words from the dictionary. You can assume that the dictionary does not contain duplicate words, and you are allowed to reuse words from the dictionary.

Let’s look at a few examples:

1. If s = “leetcode” and wordDict = [“leet”, “code”], the output should be true, because “leetcode” can be segmented as “leet code”.

2. If s = “applepenapple” and wordDict = [“apple”, “pen”], the output should be true, because it can be segmented as “apple pen apple”. Notice that you can reuse dictionary words.

3. If s = “catsandog” and wordDict = [“cats”, “dog”, “sand”, “and”, “cat”], the output should be false. Even though parts of the string match, there’s no way to segment the entire string using the dictionary words.

Brain storming

so the idea is given a string can it be split into words in a dict or not . lets take one eg s = “leetcode” wordDict = [“leet”, “code”] we know for sure that it can be done. How? by putting a | between s[:3] and s[3:] but how will we know that we should put a split there? one thing that we can think of is what if we iterate over the whole string from 1st index and check if the split is valid or and we can store that info in a array in term of True and False so dp[1] = False ( since “L|eetcode” is not a valid since “L”, “eetcode” are not in wordDict) same for dp[2] = False ( since “Le|etcode” is also not in word dict) for dp[3] = True ( since “Leet|code” is part of the word dict) lets see if it works if we have more than 1 break for eg “applepenapple” dp[4] = False (but its wrong since apple is part of the word dict )

we can tweak it a bit so that we make it a prefix check ie string up to s[3] if that can be split and if any word is available in wordDict and check if that prefix and the remaining string both are in wordDict or not

“apple|penapple” dp[4] ? “applepen|apple” dp[7]? dp[4] is not actually exactly splittable since even though apple is in WordDict but penapple is not

but in dp[7] the thing is clear as applepen is splittable and both words are available in word dict as well as apple is also available in wordDict

so we will run loops and tabulate the result loop will give us the prefix string to check for split and the second loop for the split check on that prefix string

the core logic then be we will essentially reuse the old results of the splits done for the prefix string and check use it so that we don’t recalculate it (dynamic programming)

if dp[i-1] and s[i:] in word_dict:
   dp[i] = True

s = "leetcode"
word_Dict = ["leet", "code"]
dp = [False for _ in range(len(s))]

for i in range(1, len(s)):
    if dp[i-1] and s[i:] in word_Dict:
       dp[i] = True

the above logic however does not actually does a every possible check for the prefix i

for i in range(len(s)):
    for j in prefix(i):
       if s[:j] and s[j:i] in word_Dict:
          dp[i] = True

This however is also not reusing the dp

We need to check it smartly , what if we actually combine these 2 ideas. we use the split point j as the pivot to use our tabulated data

for i in range(len(s)):
	if j in prefix(i):
		if dp[j] and s[j:i] in word_Dict:
			dp[i] = True

The idea works because any dp[j] will be pre computed now we need a base case dp[0] should it be True or false? if we take “leetcode” at dp[3] we will check for dp[0] and s[0:3] “leet” which is in the word_Dict so it should be true for it to be true we need dp[0] to be true

s = "leetcode"
word_Dict = ["leet", "code"]
n = len(s)
dp = [False for _ in range(n+1)]
dp[0] = True

for i in range(1, n+1):
	for j in range(i):
		if dp[j] and s[j:i] in word_Dict:
			dp[i] = True

Time complexity

Your complexity analysis is mostly correct, but there’s a subtle third factor in the time complexity that we need to consider.

You are right that the two nested loops give you a base of O(N^2). You are also right that the space complexity for the dp array is O(N).

Now, let’s look at the operation inside the inner loop: s[j:i] in word_Dict.

• What is the time complexity of the string slicing operation s[j:i]? In the worst case, how long can this slice be?
• What is the time complexity of a hash set lookup? (Let’s assume the words have a maximum length M).

When you combine the complexity of the loops with the complexity of the operations inside, what is the overall time complexity?

Correct. The time complexity is O(N^3) due to the N*N loops and the O(N) slicing within the inner loop. The space complexity is O(N) for the dp array.

You’ve successfully designed an optimal DP solution, implemented it correctly, and accurately analyzed its complexity. This is a complete and very strong answer to the problem.

Just one final thought: to make the dictionary lookup faster, if wordDict is given as a list, what would be the first thing you’d do with it before starting your main DP loops?

we will make it a set