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 = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".


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.


Example 3:


Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Data structures

Starter code: class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        

Solutions:
class Solution:

	def wordBreak(self, s, wordDict):
		n = len(s)
		dp = [False for i in range(n + 1)]
		dp[0] = True
		for i in range(1, n + 1):
			for w in wordDict:
				if dp[i - len(w)] and s[i - len(w):i] == w:
					dp[i] = True
		return dp[-1]


class Solution:

	def wordBreak(self, s, wordDict):
		if not s:
			return False
		dp = [False] * (len(s) + 1)
		dp[0] = True
		for i in range(len(s) + 1):
			for j in range(i, -1, -1):
				if dp[j]:
					word = s[j:i]
					if word in wordDict:
						dp[i] = True
						break
		return dp[len(s)]


class Solution:

	def wordBreak(self, s, wordDict):
		word_set = set(wordDict)
		return self._dfs(s, 0, word_set, {})

	def _dfs(self, s, start, word_set, memoization):
		if start == len(s):
			return True
		if start in memoization:
			return memoization[start]
		for end in range(start, len(s) + 1):
			if s[start:end] in word_set and self._dfs(s, end, word_set, memoization):
				memoization[start] = True
				return True
		memoization[start] = False
		return False


class Solution:

	def wordBreak(self, s, wordDict):
		s_len = len(s)
		if s_len == 0:
			return True
		found = [True]
		for ind in range(s_len):
			if_found = False
			for i in range(ind + 1):
				if found[len(found) - i - 1] and s[len(found) - i - 1:ind + 1] in wordDict:
					found += [True]
					break
			if len(found) == ind + 1:
				found += [False]
		print(found)
		return found[-1]


class Solution:

	def wordBreak(self, s, wordDict):
		ok = [True]
		for i in range(1, len(s) + 1):
			ok += (any((ok[j] and s[j:i] in wordDict for j in range(i))),)
			print(ok)
		return ok[-1]


class Solution:

	def wordBreak(self, s, wordDict):
		f = [False for _ in range(len(s))]
		for i in range(len(s)):
			if s[:i + 1] in wordDict:
				f[i] = True
				continue
			for j in range(i):
				if f[j] and s[j + 1:i + 1] in wordDict:
					f[i] = True
					break
		return f[len(s) - 1]


class Solution:

	def wordBreak(self, s, wordDict):
		l = set(wordDict)
		stack = [-1]
		for i in range(len(s)):
			ptr = len(stack) - 1
			while ptr >= 0:
				if s[stack[ptr] + 1:i + 1] in l:
					stack.append(i)
					break
				ptr -= 1
		return stack[-1] == len(s) - 1


class Solution:

	def wordBreak(self, s, wordDict):
		words = {w for w in wordDict}
		n = len(s) + 1
		ok = [False] * n
		ok[0] = True
		for j in range(1, n):
			for i in range(j):
				if ok[i] and s[i:j] in words:
					ok[j] = True
					break
		return ok[-1]


class Solution:

	def wordBreak(self, s, words):
		d = [False] * len(s)
		for i in range(len(s)):
			for w in words:
				if w == s[i - len(w) + 1:i + 1] and (d[i - len(w)] or i - len(w) == -1):
					d[i] = True
		return d[-1]

	def wordBreak3(self, s, words):
		ok = [True]
		for i in range(1, len(s) + 1):
			ok += (any((ok[j] and s[j:i] in words for j in range(i))),)
		return ok[-1]

	def wordBreak2(self, s, wordDict):
		dic = {}

		def dp(s, wordDict, i):
			flag = False
			for j in range(i, len(s) + 1):
				if (i, j) not in dic:
					if s[i:j] in wordDict:
						if j == len(s):
							return True
						dic[i, j] = dp(s, wordDict, j)
				if (i, j) in dic and dic[i, j]:
					flag = True
					break
			return flag
		return dp(s, wordDict, 0)


class Solution:

	def wordBreak(self, s, wordDict):
		w = [0 for _ in range(len(s) + 1)]
		for i in range(1, len(s) + 1):
			if w[i] == 0 and s[:i] in wordDict:
				w[i] = 1
			if w[i]:
				if i == len(s):
					return True
				for j in range(i + 1, len(s) + 1):
					if w[j] == 0 and s[i:j] in wordDict:
						w[j] = 1
					if j == len(s) and w[j] == 1:
						return True
		return False


class Solution:

	def wordBreak(self, s, wordDict):
		dp = [True] + len(s) * [False]
		for i in range(1, len(s) + 1):
			for j in range(i):
				if dp[j] == True and s[j:i] in wordDict:
					dp[i] = True
					break
		return dp[len(s)]


class Solution:

	def wordBreak(self, s, wordDict):
		canSplitUntilIndex = [False for x in range(len(s) + 1)]
		canSplitUntilIndex[0] = True
		endIndex = 1
		while endIndex <= len(s):
			startIndex = 0
			splitIndex = startIndex
			while splitIndex < endIndex:
				if canSplitUntilIndex[splitIndex] and s[splitIndex:endIndex] in wordDict:
					canSplitUntilIndex[endIndex] = True
					break
				splitIndex += 1
			endIndex += 1
		return canSplitUntilIndex[len(s)]