Word_break_dp

def wordBreak(dict, str, out=""):                                       # Recursion
	if len(str)==0:
		print(out)
		return

	for i in range(1, len(str) + 1):
		prefix = str[:i]

		if prefix in dict:
			wordBreak(dict, str[i:], out + " " + prefix)

def word_break_alternate(dict, str):                                   # Alternate way of Recursion but to avoid repetition
  return True

	for i in range(1, len(str) + 1):
		prefix = str[:i]
		if prefix in dict and wordBreak(dict, str[i:]):
			return True
	return False


def wordbreak_dp(word,dict):                                           # Dynamic programming
    m =len(word)
    T = [[False for x in range (m)] for y in range (m)]

    for l in range(1,m+1):
        for i in range(0,m-l+1):
            j = i + l-1
            str = word[i:j+1]
            if str in dict:
                T[i][j] = True
                continue

            for k in range(i+1,j+1):
                if (T[i][k - 1] != False and T[k][j] != False):
                    T[i][j] = True
                    break

    if T[0][m-1] == False:
        return False
    else:
        return True