Given a string A and a dictionary of n words B, find out if A can be segmented into a space-separated sequence of dictionary words.
Note: From the dictionary B each word can be taken any number of times and in any order.
Example 1:
Input:
n = 12
B = { "i", "like", "sam",
"sung", "samsung", "mobile",
"ice","cream", "icecream",
"man", "go", "mango" }
A = "ilike"
Output:
1
Explanation:
The string can be segmented as "i like".
Example 2:
Input:
n = 12
B = { "i", "like", "sam",
"sung", "samsung", "mobile",
"ice","cream", "icecream", 
"man", "go", "mango" }
A = "ilikesamsung"
Output:
1
Explanation:
The string can be segmented as 
"i like samsung" or "i like sam sung".
 
Your Task:
Complete wordBreak() function which takes a string and list of strings as a parameter and returns 1 if it is possible to break words, else return 0. You don't need to read any input or print any output, it is done by driver code.
Expected time complexity: O(s^{2})
Expected auxiliary space: O(s) , where s = length of string A
 
Constraints:
1 ≤ N ≤ 12
1 ≤ s ≤ 1100 , where s = length of string A

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



def wordBreak(line, dictionary):

    # Complete this function

Solutions:
def wordBreak(line, dictionary):
	dp = [False] * (len(line) + 1)
	dp[len(line)] = True
	for i in range(len(line) - 1, -1, -1):
		for word in dictionary:
			if len(word) + i <= len(line) and line[i:i + len(word)] == word:
				dp[i] = dp[i + len(word)]
			if dp[i]:
				break
	return dp[0]


def solve(start, end, line, dictionary):
	if start >= end:
		return True
	for i in range(start, end):
		if line[start:i + 1] in dictionary:
			if solve(i + 1, end, line, dictionary):
				return True
	return False

def solve_memo(start, end, line, dictionary, F):
	if start >= end:
		return True
	if F[start] != -1:
		return F[start]
	for i in range(start, end):
		if line[start:i + 1] in dictionary:
			if solve_memo(i + 1, end, line, dictionary, F):
				F[start] = True
				return F[start]
	F[start] = False
	return F[start]

def solve_tab(n, line, dictionary):
	F = [False] * (n + 1)
	F[n] = True
	for start in range(n - 1, -1, -1):
		for i in range(start, n):
			if line[start:i + 1] in dictionary:
				if F[i + 1]:
					F[start] = True
					break
	return F[0]

def wordBreak(line, dictionary):
	n = len(line)
	return solve_tab(n, line, dictionary)


def solve(start, end, line, dictionary):
	if start >= end:
		return True
	for i in range(start, end):
		if line[start:i + 1] in dictionary:
			if solve(i + 1, end, line, dictionary):
				return True
	return False

def wordBreak(line, dictionary):
	n = len(line)
	return solve(0, n, line, dictionary)


def wordBreak(s, dictionary):
	dp = [False] * (len(s) + 1)
	dp[len(s)] = True
	for i in range(len(s) - 1, -1, -1):
		for w in dictionary:
			if i + len(w) <= len(s) and s[i:i + len(w)] == w:
				dp[i] = dp[i + len(w)]
				if dp[i]:
					break
	return dp[0]


def wordBreak(A, B):
	n = len(A)
	dp = [0] * (n + 1)
	dp[0] = 1
	for i in range(1, n + 1):
		for j in range(i - 1, -1, -1):
			if dp[j] and A[j:i] in B:
				dp[i] = 1
				break
	return dp[n]


def wordBreak(line, dictionary):
	s = set(dictionary)
	n = len(line)
	dp = [0 for _ in range(n)]
	for i in range(n):
		for j in range(i + 1):
			w = line[j:i + 1]
			if w in s:
				if j > 0:
					dp[i] += dp[j - 1]
				else:
					dp[i] += 1
	return dp[n - 1]


def solve1(ws, i, n, line, dic, s, s1):
	if i == n:
		if line[ws:i] in s:
			s1.add(line[ws:i])
			return True
		return False
	if line[ws:i] in s1:
		return True
	if line[ws:i] in s and line[i:] in s:
		s1.add(line[ws:i])
		s1.add(line[i:])
		return True
	elif line[ws:i] in s:
		x = solve(i, i + 1, n, line, dic, s, s1) or solve(ws, i + 1, n, line, dic, s, s1)
		if x == True:
			s1.add(line[ws:i])
		return x
	else:
		y = solve(ws, i + 1, n, line, dic, s, s1)
		if y == True:
			s1.add(line[ws:i])
		return y

def solve(line, s):
	if len(line) == 0:
		return True
	for i in range(len(line)):
		x = line[:i + 1]
		if x in s:
			ans = solve(line[i + 1:], s)
			if ans == 1:
				return True
	return False

def wordBreak(line, dictionary):
	s1 = set()
	s = set(dictionary)
	return solve(line, s)


def wordBreak(line, dictionary):
	n = len(line)
	dp = [False for _ in range(n + 1)]
	dp[0] = True
	for i in range(n + 1):
		for j in range(i):
			if dp[j] and line[j:i] in dictionary:
				dp[i] = True
				break
	return dp[n]


def wordBreak(line, dictionary):

	def helper(ind):
		if ind == len(line):
			return True
		for i in range(ind, len(line)):
			if line[ind:i + 1] in dictionary:
				if helper(i + 1):
					return True
		return False
	return helper(0)


def wordBreak(line, dictionary):
	n = len(line)
	dic_len = [len(key) for key in dictionary]
	dp = [False] * (n + 1)
	dp[0] = True
	for i in range(n + 1):
		if dp[i]:
			for j in range(len(dic_len)):
				if line[i:i + dic_len[j]] == dictionary[j]:
					dp[i + dic_len[j]] = True
	return dp[-1]


def wordBreak(line, dictionary):
	d = {}
	data = {}
	for i in dictionary:
		d[i] = None

	def is_valid(line):
		if len(line) == 0:
			return True
		if line in data:
			return data[line]
		for i in range(len(line) + 1):
			if line[:i] in d:
				if is_valid(line[i:]):
					data[line] = True
					return data[line]
		data[line] = False
		return data[line]
	return is_valid(line)


from collections import defaultdict

def wordBreak(line, dictionary):
	d = defaultdict(lambda : 0)
	for x in dictionary:
		d[x] += 1
	dp = [0] * (len(line) + 1)
	dp[0] = 1
	for i in range(len(line)):
		for j in range(i + 1):
			if line[j:i + 1] in d:
				dp[i + 1] += dp[j]
	return dp[-1]


def wordBreak(line, dictionary):
	word_set = set(dictionary)
	n = len(line)
	dp = [False] * (n + 1)
	dp[0] = True
	for i in range(1, n + 1):
		for j in range(i):
			if dp[j] and line[j:i] in word_set:
				dp[i] = True
	return dp[n]


def wordBreak(line, l):
	r = []

	def ax(s):
		if s == '':
			return 1
		for i in range(len(s)):
			z = s[:i + 1]
			if z in l:
				if ax(s[i + 1:]):
					return 1
		return 0
	return ax(line)


def wordBreak(s, wordDict):
	breakpoints = []
	for i in range(len(s)):
		if s[:i + 1] in wordDict:
			breakpoints.append(i)
			continue
		for j in breakpoints:
			if s[j + 1:i + 1] in wordDict:
				breakpoints.append(i)
	return 1 if len(s) - 1 in breakpoints else 0


def solve(line, i, d_set, n):
	if i == n:
		return True
	temp = ''
	for j in range(i, n):
		temp += line[j]
		if temp in d_set:
			res = solve(line, j + 1, d_set, n)
			if res is True:
				return True
	return False

def wordBreak(line, dictionary):
	d_set = set()
	n = len(line)
	dp = [False] * (n + 1)
	for word in dictionary:
		d_set.add(word)
	dp[0] = True
	for i in range(n + 1):
		for j in range(i):
			if dp[j] and line[j:i] in d_set:
				dp[i] = True
				break
	return dp[n]


def wordBreak(line, dictionary):
	size = len(line)
	if size == 0:
		return True
	for i in range(size + 1):
		if line[0:i] in dictionary and wordBreak(line[i:size], dictionary):
			return True
	return False


def wordBreak(s, wordDict):
	words = set(wordDict)
	memo = {}

	def dp(index):
		if index == len(s):
			return True
		if index in memo:
			return memo[index]
		string = ''
		for i in range(index, len(s)):
			string += s[i]
			if string in words:
				if dp(i + 1):
					memo[index] = True
					return True
		memo[index] = False
		return False
	return dp(0)


def wordBreak(line, dictionary):
	stateMap = [0 for _ in range(len(line) + 1)]
	stateMap[0] = 1
	for rightSide in range(1, len(stateMap)):
		for leftSide in range(rightSide):
			if line[leftSide:rightSide] in dictionary and stateMap[leftSide]:
				stateMap[rightSide] = 1
				break
	return stateMap[-1]


def wordBreak(line, dictionary):

	def f(s, b, a):
		if s == '':
			return True
		for j in range(len(s)):
			if s[:j + 1] in b and f(s[j + 1:], b, a):
				return True
		return False
	return f(line, dictionary, line)


def wordBreak(line, dictionary):
	d = set(dictionary)
	ans = function(line, d)
	return ans

def function(line, d):
	if len(line) == 0:
		return True
	for i in range(0, len(line) + 1):
		if line[0:i] in d:
			ans1 = function(line[i:], d)
			if ans1 is True:
				return True
	return False


def wordBreak(s, dictionary):
	n = len(s)
	dp = [False] * (n + 1)
	dp[0] = True
	matched_index = [-1]
	for i in range(n + 1):
		for j in range(i):
			if dp[j] and s[j:i] in dictionary:
				dp[i] = 1
				matched_index.append(i)
				break
	return dp[n]


def wordBreak(line, dictionary):
	n = len(line)
	dp = [-1 for i in range(n + 1)]

	def rec(idx):
		if idx >= n:
			return True
		if dp[idx] != -1:
			return dp[idx]
		for i in range(n - idx + 1):
			if line[idx:idx + i] in dictionary:
				dp[idx] = rec(idx + i)
				if dp[idx]:
					return True
		dp[idx] = False
		return dp[idx]
	return rec(0)


def wordBreak(line, dictionary):
	n = len(line)

	def solve(idx):
		if idx >= n:
			return 1
		for i in range(1, n - idx + 1):
			sub = line[idx:idx + i]
			if sub in dictionary:
				if solve(idx + i) == 1:
					return 1
		return 0
	return solve(0)


def wordBreak(line, dictionary):

	def solve(idx, s, mp):
		if idx >= len(s):
			return 1
		for i in range(1, len(s) - idx + 1):
			sub = s[idx:idx + i]
			if sub in mp:
				if solve(idx + i, s, mp) == 1:
					return 1
		return 0
	return solve(0, line, dictionary)


def wordBreak(line, dictionary):
	if not line:
		return True
	for i in range(len(line) + 1):
		if line[:i] in dictionary and wordBreak(line[i:], dictionary):
			return True
	return False


def wordBreak(word, dictionary):
	size = len(word)
	if size == 0:
		return True
	for i in range(300):
		if word[0:i] in dictionary and wordBreak(word[i:size], dictionary):
			return True
	return False


dp = [[None for i in range(0, 14)] for j in range(0, 1102)]

def find(line, i, dictionary):
	if i == len(line):
		return 1
	for j in range(0, len(dictionary)):
		if dp[i][j] is not None:
			continue
		else:
			if line[i:len(line)].startswith(dictionary[j]):
				a = find(line, i + len(dictionary[j]), dictionary)
				if a == 1:
					return 1
			dp[i][j] = 0
	return 0

def wordBreak(line, dictionary):
	global dp
	dp = [[None for i in range(0, 14)] for j in range(0, 1102)]
	return find(line, 0, dictionary)


def check(l, checked):
	if l in checked:
		return checked[l]
	for i in range(len(l) - 1):
		if check(l[:i + 1], checked) and check(l[i + 1:], checked):
			checked[l] = True
			return True
	checked[l] = False
	return False

def wordBreak(line, dictionary):
	checked = {}
	for word in dictionary:
		checked[word] = True
	if check(line, checked):
		return 1
	return 0


def util(line, d):
	if len(line) == 0:
		return 1
	if d.get(line) == 1:
		return 1
	for i in range(1, len(line)):
		if d.get(line[:i]) != None:
			if util(line[i:], d) == 1:
				return 1
	return 0

def wordBreak(line, dictionary):
	d = {}
	for i in dictionary:
		d[i] = 1
	return util(line, d)


def wordBreak(A, B):
	n = len(A)
	dp = [False] * (n + 1)
	dp[-1] = True
	for i in range(n - 1, -1, -1):
		for word in B:
			x = len(word)
			if i + x <= n and A[i:i + x] == word:
				dp[i] = dp[i + x]
			if dp[i]:
				break
	return dp[0]


def wordBreak(line, dictionary):
	dic = set(dictionary)

	def wordb(st, line, n):
		if st >= n:
			return True
		val = False
		for i in range(st + 1, n + 1):
			if line[st:i] in dic:
				val = wordb(i, line, n)
			if val == True:
				return True
		return False
	n = len(line)
	return wordb(0, line, n)


def wordBreak(line, dictionary):
	dp = [0 for i in range(len(line) + 1)]
	dp[0] = 1
	for i in range(1, len(dp)):
		for j in range(i):
			if line[j:i] in dictionary and dp[j] == 1:
				dp[i] = 1
				break
	return dp[-1]


def wordBreak(line, dicti):
	n = len(line)
	dp = [0] * n
	for i in range(n):
		for j in range(i + 1):
			word = line[j:i + 1]
			if word in dicti:
				if j > 0:
					dp[i] += dp[j - 1]
				else:
					dp[i] += 1
	return dp[-1]


def wordBreak(s, wordDict):
	if not s:
		return True
	for i in range(1, len(s) + 1):
		if s[:i] in wordDict and wordBreak(s[i:], wordDict):
			return True
	return False


def check(s, wordDict, i, n, q, t, m):
	if q == s:
		return True
	for j in range(i, n):
		t += s[j]
		if t in wordDict:
			q += t
			sz = len(t)
			i += sz
			m = t
			t = ''
			if check(s, wordDict, i, n, q, t, m):
				return True
			i -= sz
			q = q[:-sz]
			t = m
	return False

def wordBreak(s, dictionary):
	wordDict = list(dictionary)
	n = len(s)
	sz = len(wordDict)
	(q, t, m) = ('', '', '')
	cnt = 0
	return check(s, wordDict, 0, n, q, t, m)


def helper(s, d):
	if not s:
		return True
	for i in range(len(s)):
		if s[:i + 1] in d:
			if helper(s[i + 1:], d):
				return True
	return False

def wordBreak(line, dictionary):
	return helper(line, set(dictionary))


def wordBreak(line, dic):
	n = len(line)
	if n == 0:
		return True
	if line in dic:
		return True
	for i in range(1, n):
		if line[:i] in dic and wordBreak(line[i:], dic):
			return True
	return False


def wordBreak(line, dictionary):

	def wordBreak(word, dictionary, memo=dict()):
		if len(word) == 0:
			return True
		if word in memo:
			return memo[word]
		for i in dictionary:
			if word.startswith(i):
				tempWord = word[len(i):]
				temp = wordBreak(tempWord, dictionary, memo)
				if temp:
					memo[word] = True
					return memo[word]
		memo[word] = False
		return memo[word]
	return wordBreak(line, dictionary)


def wordBreak(s, wordDict):
	n = len(s)
	dp = [False] * (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 wordDict:
				dp[i] = True
				break
	return dp[n]


class TrieNode:

	def __init__(self):
		self.children = {}
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = TrieNode()
		self.failed = [False] * 100000

	def insert(self, key):
		curr = self.root
		for i in key:
			if i not in curr.children:
				curr.children[i] = TrieNode()
			curr = curr.children[i]
		curr.isEndOfWord = True

	def search(self, s, start):
		curr = self.root
		if self.failed[start]:
			return False
		if start >= len(s):
			return True
		for i in range(start, len(s)):
			if s[i] not in curr.children:
				return False
			curr = curr.children[s[i]]
			if curr.isEndOfWord:
				if self.search(s, i + 1):
					return True
				self.failed[i + 1] = True
		return False

def wordBreak(line, dictionary):
	trie = Trie()
	for i in dictionary:
		trie.insert(i)
	return trie.search(line, 0)


def wordBreak(line, dictionary):
	dic = {}
	for i in dictionary:
		dic[i] = 1

	def manu(dic, word):
		if word == '':
			return True
		if word in dp:
			return dp[word]
		x = False
		for i in range(len(word)):
			if word[:i + 1] in dic:
				x = x or manu(dic, word[i + 1:])
		dp[word] = x
		return x
	dp = {}
	return manu(dic, line)


def solve(i, j, line, dictionary, dp):
	if i > j:
		return 1
	if i == j:
		return line[i] in dictionary
	if dp[i][j] != -1:
		return dp[i][j]
	currans = 0
	for p in range(i, j + 1):
		if line[i:p + 1] in dictionary:
			currans = currans or solve(p + 1, j, line, dictionary, dp)
	dp[i][j] = currans
	return dp[i][j]

def wordBreak(line, dictionary):
	dictionary = set(dictionary)
	dp = [[-1 for i in range(len(line))] for y in range(len(line))]
	return solve(0, len(line) - 1, line, dictionary, dp)


def wordBreak(line, dictionary):
	dp = [-1 for i in range(len(line))]
	return helper(0, line, dictionary, dp)

def helper(ind, line, dictionary, dp):
	if ind >= len(line):
		return 1
	if dp[ind] != -1:
		return dp[ind]
	temp = ''
	for i in range(ind, len(line)):
		temp += line[i]
		if temp in dictionary:
			if helper(i + 1, line, dictionary, dp):
				dp[ind] = 1
				return dp[ind]
	dp[ind] = 0
	return dp[ind]


def wordBreak(line, dictionary):
	hash_set = set()
	for word in dictionary:
		hash_set.add(word)
	return helper(line, hash_set, 0)

def helper(line, hash_set, index):
	if index == len(line):
		return True
	for i in range(index, len(line) + 1):
		if line[index:i] in hash_set and helper(line, hash_set, i):
			return True
	return False


def util(cw, rem, d, dp):
	if rem in dp:
		return dp[rem]
	if rem == '':
		return cw in d or cw == ''
	for idx in range(len(rem)):
		ch = rem[idx]
		cw += ch
		if cw in d and util('', rem[idx + 1:], d, dp):
			dp[rem] = True
			return dp[rem]
	dp[rem] = False
	return dp[rem]

def wordBreak(line, dictionary):
	dp = {}
	return util('', line, dictionary, dp)


def helper(idx, A, B, dp):
	if idx >= len(A):
		return 1
	if dp[idx] != -1:
		return dp[idx]
	dp[idx] = 0
	for i in range(idx, len(A)):
		if A[idx:i + 1] in B:
			if helper(i + 1, A, B, dp):
				dp[idx] = 1
				break
	return dp[idx]

def wordBreak(line, dictionary):
	dp = [-1] * len(line)
	helper(0, line, dictionary, dp)
	return dp[0]


def fun(s, arr):
	if len(s) == 0:
		return True
	temp = ''
	for i in range(len(s)):
		temp += s[i]
		if temp in arr:
			if fun(s[i + 1:], arr):
				return True
	return False

def wordBreak(s, arr):
	return fun(s, arr)


def rec(line, st):
	if line == '':
		return True
	for i in range(len(line)):
		first = line[:i + 1]
		if first in st:
			second = line[i + 1:]
			if rec(second, st):
				return True
	return False

def wordBreak(line, dictionary):
	st = set(dictionary)
	if rec(line, st):
		return 1
	return 0


def wordBreak(line, dictionary):
	if line == '':
		return 1
	else:
		return any([line[:i] in dictionary and wordBreak(line[i:], dictionary) for i in range(1, len(line) + 1)])