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. 
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(n*l+|A|^{2}) where l is the leght of longest string present in the dictionary and |A| is the length of string A
Expected auxiliary space: O(|A| + k) , where k = sum of length of all strings present in B
 
Constraints:
1 <= N <= 12
1 <= s <=1000 , where s = length of string A
 The length of each word is less than 15.

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def wordBreak(self, A, B):

        # Complete this function

Solutions:
class TrieNode:

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

class Solution:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word):
		curr = self.root
		for ch in word:
			if ch not in curr.children:
				curr.children[ch] = TrieNode()
			curr = curr.children[ch]
		curr.endOfWord = True

	def search(self, word: str) -> bool:
		curr = self.root
		for ch in word:
			if ch not in curr.children:
				return False
			curr = curr.children[ch]
		return curr.endOfWord

	def isfound(self, word):
		curr = self.root
		n = len(word)
		if n == 0:
			return 1
		for i in range(1, n + 1):
			if self.search(word[:i]) and self.isfound(word[i:]):
				return 1
		return 0

	def wordBreak(self, A, B):
		for word in B:
			self.insert(word)
		ans = self.isfound(A)
		return ans


class Node:

	def __init__(self, ch):
		self.data = ch
		self.childrens = [None] * 26
		self.is_terminal = False

	def __str__(self) -> str:
		return self.data

class Trie:

	def __init__(self):
		self.root = Node('\x00')

	def insert(self, root, word):
		for ch in word:
			idx = ord(ch) - ord('a')
			if root.childrens[idx] is None:
				root.childrens[idx] = Node(ch)
			root = root.childrens[idx]
		root.is_terminal = True

	def search(self, root, word):
		for ch in word:
			idx = ord(ch) - ord('a')
			if root.childrens[idx] is None:
				return False
			root = root.childrens[idx]
		return root and root.is_terminal

class Solution:

	def solve(self, t, word):
		n = len(word)
		if n == 0:
			return 1
		for i in range(1, n + 1):
			if t.search(t.root, word[:i]):
				if self.solve(t, word[i:]):
					return 1
		return 0

	def wordBreak(self, A, B):
		t = Trie()
		for word in B:
			t.insert(t.root, word)
		return self.solve(t, A)


class Solution:

	def wordBreak(self, line, dictionary):

		def postfixx(line, dictionary, i):
			if line[i:] in dictionary:
				return 1
			l = len(line[i:])
			str1 = ''
			for x in range(i, i + l):
				str1 += line[x]
				if str1 in dictionary:
					z = postfixx(line, dictionary, x + 1)
					if z == 1:
						return 1
			return 0
		return postfixx(line, dictionary, 0)


class trieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEnd = False

class trie:

	def __init__(self):
		self.root = trieNode()

	def insert(self, word):
		r = self.root
		cnt = 1
		for i in word:
			if r.children[ord(i) - ord('a')] == None:
				r.children[ord(i) - ord('a')] = trieNode()
			r = r.children[ord(i) - ord('a')]
			if cnt == len(word):
				r.isEnd = True
			cnt += 1

def solver(root, string, curr, i):
	r = root
	if i >= len(string):
		return True
	s = ''
	while i < len(string):
		if root != None:
			s += string[i]
			if root.children[ord(string[i]) - ord('a')] and root.children[ord(string[i]) - ord('a')].isEnd:
				if solver(r, string, curr + ' ' + s, i + 1):
					return True
		else:
			break
		root = root.children[ord(string[i]) - ord('a')]
		i += 1
	return False

class Solution:

	def wordBreak(self, s, dictionary):
		T = trie()
		for i in dictionary:
			T.insert(i)
		return solver(T.root, s, '', 0)


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, root, val):
		temp = root
		for ch in val:
			i = ord(ch) - ord('a')
			if temp.children[i] == None:
				temp.children[i] = TrieNode()
			temp = temp.children[i]
		temp.isEndOfWord = True

	def search(self, root, key):
		temp = root
		for ch in key:
			i = ord(ch) - ord('a')
			if temp.children[i] == None:
				return False
			temp = temp.children[i]
		return temp.isEndOfWord

	def searchSubStr(self, root, word):
		n = len(word)
		temp = root
		if n == 0:
			return True
		for i in range(1, n + 1):
			if self.search(root, word[:i]) and self.searchSubStr(root, word[i:]):
				return True
		return False

class Solution:

	def wordBreak(self, A, B):
		t = Trie()
		for word in B:
			t.insert(t.root, word)
		return t.searchSubStr(t.root, A)


class Solution:

	def checkWordBreak(strr, root):
		n = len(strr)
		if n == 0:
			return True
		for i in range(1, n + 1):
			if root.search(root, strr[:i]) and Solution.checkWordBreak(strr[i:], root):
				return True
		return False

	def wordBreak(self, A, B):
		t = TrieNode()
		for str in B:
			t.insert(t, str)
		return Solution.checkWordBreak(A, t)

class TrieNode:

	def __init__(self):
		self.children = [None] * 27
		self.isLeaf = False

	def insert(self, root, key):
		key = str(key)
		pCrawl = root
		for i in key:
			index = ord(i) - 97
			if pCrawl.children[index] == None:
				pCrawl.children[index] = TrieNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isLeaf = True

	def search(self, root, key):
		pCrawl = root
		for i in key:
			index = ord(i) - 97
			if pCrawl.children[index] == None:
				return False
			pCrawl = pCrawl.children[index]
		if pCrawl and pCrawl.isLeaf:
			return True


class Solution:

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


class Solution:

	def wordBreak(self, 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]


import collections
import functools

class Solution:

	def wordBreak(self, A, B):
		self.n = len(A)
		T = lambda : collections.defaultdict(T)
		self.trie = T()
		for w in B:
			functools.reduce(dict.__getitem__, w, self.trie)['#'] = True
		return self.dfs(A, 0)

	def dfs(self, word, idx):
		cur = self.trie
		ans = 0
		if idx == self.n:
			return 1
		for i in range(idx, self.n):
			if word[i] in cur:
				cur = cur[word[i]]
				if cur['#'] == True:
					ans = ans or self.dfs(word, i + 1)
			else:
				break
		return ans


class Solution:

	def wordBreak(self, A, B):

		class Trie:

			def __init__(self):
				self.root = TrieNode()

			def insert(self, word):
				root = self.root
				for i in word:
					ind = self.chartoind(i)
					if root.children[ind] == None:
						root.children[ind] = TrieNode()
					root = root.children[ind]
				root.IsEndOfWord = True

			def search(self, word):
				root = self.root
				for i in word:
					ind = self.chartoind(i)
					if root.children[ind] == None:
						return False
					root = root.children[ind]
				return root.IsEndOfWord

			def chartoind(self, x):
				return ord(x) - ord('a')

			def isExists(self, word):
				root = self.root
				if len(word) == 0:
					return True
				x = word[0]
				if root.children[self.chartoind(x)] == None:
					return False
				for i in range(len(word) + 1):
					if self.search(word[:i]) and self.isExists(word[i:]):
						return True
				return False

		class TrieNode:

			def __init__(self):
				self.children = [None] * 26
				self.IsEndOfWord = False
		t = Trie()
		for i in B:
			t.insert(i)
		return t.isExists(A)


class Trienode:

	def __init__(self):
		self.childrens = [None] * 26
		self.endofword = False

class Solution:

	def __init__(self):
		self.root = Trienode()

	def insert(self, word):
		curr = self.root
		for i in word:
			idx = ord(i) - ord('a')
			if curr.childrens[idx] is None:
				curr.childrens[idx] = Trienode()
			curr = curr.childrens[idx]
		curr.endofword = True

	def search(self, key):
		curr = self.root
		for i in key:
			idx = ord(i) - 97
			if not curr.childrens[idx]:
				return False
			else:
				curr = curr.childrens[idx]
		if curr.endofword:
			return 1
		else:
			return 0

	def isfound(self, word):
		curr = self.root
		n = len(word)
		if n == 0:
			return 1
		for i in range(1, n + 1):
			if self.search(word[:i]) and self.isfound(word[i:]):
				return 1
		return 0

	def wordBreak(self, a, b):
		for i in b:
			self.insert(i)
		ans = self.isfound(a)
		return ans


class TrieNode:

	def __init__(self):
		self.next = {}
		self.isEnd = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, s):
		curr = self.root
		for c in s:
			if c not in curr.next:
				curr.next[c] = TrieNode()
			curr = curr.next[c]
		curr.isEnd = True

	def util(self, ptr, s, i, n):
		if i == n:
			return ptr.isEnd
		if ptr.isEnd and self.util(self.root, s, i, n):
			return True
		if s[i] not in ptr.next:
			return False
		return self.util(ptr.next[s[i]], s, i + 1, n)

	def isPossible(self, s):
		return self.util(self.root, s, 0, len(s))

class Solution:

	def wordBreak(self, A, B):
		trie = Trie()
		for s in B:
			trie.insert(s)
		return trie.isPossible(A)


from functools import lru_cache

class Solution:

	def wordBreak(self, A, B):
		N = len(A)
		dp = [0 for i in range(N + 1)]
		dp[0] = 1
		precompute = {}
		for w in B:
			precompute[w] = set()
		for i in range(N):
			curr = ''
			for j in range(i, N):
				curr += A[j]
				if curr in precompute:
					precompute[curr].add((i, j + 1))
		for i in range(1, N + 1):
			found = False
			for word in B:
				size = len(word)
				if i - size >= 0 and dp[i - size] == 1 and ((i - size, i) in precompute[word]):
					dp[i] = 1
					break
		return dp[N]


class Solution:

	def wordBreak(self, word, words):
		trie = self.buildTrie(words)
		return self.isConcatenatedWord(0, 0, word, trie, trie)

	def isConcatenatedWord(self, index, wordlen, word, node, trie):
		if index == len(word):
			if wordlen == 0:
				return True
			return False
		if word[index] not in node.next:
			return False
		node = node.next[word[index]]
		index += 1
		wordlen += 1
		if node.isWord:
			if self.isConcatenatedWord(index, 0, word, trie, trie):
				return True
		return self.isConcatenatedWord(index, wordlen, word, node, trie)

	def buildTrie(self, words):
		root = Node('')
		for word in words:
			node = root
			for char in word:
				if char not in node.next:
					node.next[char] = Node(char)
				node = node.next[char]
			node.isWord = True
		return root

class Node:

	def __init__(self, char, isWord=False):
		self.char = char
		self.isWord = isWord
		self.next = dict()


def words(B, A, cur, index):
	if index == len(A):
		return cur == '' or cur in B
	cur = cur + A[index]
	if cur in B:
		if words(B, A, '', index + 1):
			return True
	return words(B, A, cur, index + 1)

class Solution:

	def wordBreak(self, A, B):
		ans = []
		if words(B, A, '', 0):
			return 1
		else:
			return 0


class Solution:

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

		def finder(target, words, memo):
			if target in memo:
				return memo[target]
			if target == '':
				return True
			for i in words:
				if i == target[0:len(i)]:
					suffix = target[len(i):]
					if finder(suffix, words, memo):
						memo[target] = True
						return True
			memo[target] = False
			return False
		return finder(s, wordDict, memo)


class Solution:

	def wordBreak(self, A, B):
		if len(A) == 0 or A in B:
			return 1
		else:
			for i in range(len(A)):
				if A[0:i] in B and self.wordBreak(A[i:], B):
					return True
			return False


class Solution:

	def wordBreak(self, A, B):
		q = [0]
		mp = set(B)
		visited = set()
		while q:
			length = len(q)
			while length > 0:
				idx = q.pop(0)
				if idx in visited:
					length -= 1
					continue
				visited.add(idx)
				if idx == len(A):
					return 1
				for x in range(idx, len(A)):
					val = A[idx:x + 1]
					if val in mp:
						q.append(x + 1)
				length -= 1
		return 0


class Solution:

	def solve(self, a, n, d, i, ans):
		if i == n:
			return True
		if i in ans:
			return ans[i]
		for j in range(i + 1, n + 1):
			if a[i:j] in d and self.solve(a, n, d, j, ans):
				ans[i] = True
				return True
		ans[i] = False
		return False

	def wordBreak(self, A, B):
		n = len(A)
		d = {i: True for i in B}
		ans = {}
		return self.solve(A, n, d, 0, ans)


class Trie:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

def insert(root, key):
	for k in key:
		index = ord(k) - 97
		if not root.children[index]:
			root.children[index] = Trie()
		root = root.children[index]
	root.isEndOfWord = True

def check(root, key):
	for k in key:
		index = ord(k) - 97
		if not root.children[index]:
			return False
		root = root.children[index]
	if root.isEndOfWord:
		return True
	return False

def solve(root, key):
	n = len(key)
	if n == 0:
		return True
	for i in range(1, n + 1):
		if check(root, key[:i]) and solve(root, key[i:]):
			return True
	return False

class Solution:

	def wordBreak(self, A, B):
		root = Trie()
		for i in B:
			insert(root, i)
		if solve(root, A):
			return 1
		return 0


class TrieNode:

	def __init__(self):
		self.d = {}
		self.isEnd = False

class Solution:

	def wordBreak(self, A, B):
		root = TrieNode()
		for word in B:
			curr = root
			for letter in word:
				if letter not in curr.d:
					curr.d[letter] = TrieNode()
				curr = curr.d[letter]
			curr.isEnd = True

		def search(word, root):
			curr = root
			for i in word:
				if i in curr.d:
					curr = curr.d[i]
				else:
					return False
			return curr.isEnd
		n = len(A)
		l = [False] * n
		l.append(True)
		for i in range(n - 1, -1, -1):
			for j in range(i, n + 1):
				if i == j:
					continue
				if search(A[i:j], root):
					l[i] = l[j]
				if l[i]:
					break
		return l[0]


class Solution:

	def wordBreak(self, A, B):

		class TrieNode:

			def __init__(self):
				self.child = {}
				self.Eow = False

		def insert(word, Trie):
			for c in word:
				if c not in Trie.child:
					Trie.child[c] = TrieNode()
				Trie = Trie.child[c]
			Trie.Eow = True

		def search(word, Trie):
			for w in word:
				if w in Trie.child:
					Trie = Trie.child[w]
				else:
					return False
			return Trie.Eow

		def trav(A, i, Trie):
			if i == len(A):
				return True
			for j in range(i + 1, len(A) + 1):
				if search(A[i:j], Trie) and trav(A, j, Trie):
					return True
			return False
		Trie = TrieNode()
		for word in B:
			insert(word, Trie)
		return trav(A, 0, Trie)


class Solution:

	def wordBreak(self, s, wordd):
		dp = [False] * (len(s) + 1)
		dp[len(s)] = True
		for i in range(len(s) - 1, -1, -1):
			for w in wordd:
				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]


class TrieNode:

	def __init__(self):
		self.child = [None] * 26
		self.endOfWord = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def _chatToIndex(self, char):
		return ord(char) - ord('a')

	def insert(self, key):
		node = self.root
		for i in key:
			index = ord(i) - ord('a')
			if not node.child[index]:
				node.child[index] = TrieNode()
			node = node.child[index]
		node.endOfWord = True

	def search(self, key):
		node = self.root
		for i in key:
			index = ord(i) - ord('a')
			if not node.child[index]:
				return False
			node = node.child[index]
		return node.endOfWord

class Solution:

	def __init__(self):
		self.count = 0
		self.trie = None

	def helper(self, A, pos, n):
		if pos >= n:
			if A == '':
				self.count += 1
			return
		if self.trie.search(A[:pos + 1]):
			self.helper(A[pos + 1:], 0, n - pos - 1)
		self.helper(A, pos + 1, n)

	def wordBreak(self, A, B):
		self.trie = Trie()
		for i in B:
			self.trie.insert(i)
		self.helper(A, 0, len(A))
		return self.count

class Solution:

	def __init__(self):
		self.count = 0
		self.trie = None

	def helper(self, A, n):
		if n == 0:
			return True
		for i in range(1, n + 1):
			if self.trie.search(A[:i]) and self.helper(A[i:], n - i):
				self.count += 1

	def wordBreak(self, A, B):
		self.trie = Trie()
		for i in B:
			self.trie.insert(i)
		self.helper(A, len(A))
		return self.count

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


class TrieNode:

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

	def insertWord(self, word):
		root = self
		for letter in word:
			if letter not in root.children:
				root.children[letter] = TrieNode()
			root = root.children[letter]
		root.isEndOfWord = True

class Solution:

	def resultantFunc(self, A, B, root, i=0):
		curr = root
		while i < len(A):
			if A[i] not in curr.children:
				return False
			curr = curr.children[A[i]]
			if curr.isEndOfWord:
				if i == len(A) - 1 or self.resultantFunc(A, B, root, i + 1):
					return True
			i += 1
		return False

	def wordBreak(self, A, B, i=0):
		root = TrieNode()
		for word in B:
			root.insertWord(word)
		return self.resultantFunc(A, B, root)


class Solution:

	def wordBreak(self, A, B):
		dp = [True] + [False] * len(A)
		for i in range(1, len(A) + 1):
			for word in B:
				if A[:i].endswith(word):
					dp[i] |= dp[i - len(word)]
		return dp[-1]


MAX_CHAR = 256

class Node:

	def __init__(self):
		self.children = [None] * MAX_CHAR
		self.is_end = False

def insert(root, word):
	curr = root
	for ch in word:
		idx = ord(ch)
		if not curr.children[idx]:
			curr.children[idx] = Node()
		curr = curr.children[idx]
	curr.is_end = True

def search(root, word):
	curr = root
	for ch in word:
		idx = ord(ch)
		if not curr.children[idx]:
			return False
		curr = curr.children[idx]
	return curr.is_end

class Solution:

	def check_word_break(self, root, A):
		n = len(A)
		if n == 0:
			return True
		for i in range(1, n + 1):
			if search(root, A[:i]) and self.check_word_break(root, A[i:]):
				return True
		return False

	def wordBreak(self, A, B):
		root = Node()
		for word in B:
			insert(root, word)
		return self.check_word_break(root, A)


class TrieNode:

	def __init__(self):
		self.links = [None] * 26
		self.endOfWord = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, key):
		curr = self.root
		for ele in key:
			if not curr.links[ord(ele) - ord('a')]:
				curr.links[ord(ele) - ord('a')] = TrieNode()
			curr = curr.links[ord(ele) - ord('a')]
		curr.endOfWord = True

class Solution:

	def wordBreak(self, A, B):
		t = Trie()
		for ele in B:
			t.insert(ele)

		def recur(ind, curr):
			if ind == len(A):
				if curr.endOfWord:
					return 1
				else:
					return 0
			if curr.links[ord(A[ind]) - ord('a')]:
				if curr.links[ord(A[ind]) - ord('a')].endOfWord:
					return recur(ind + 1, curr.links[ord(A[ind]) - ord('a')]) or recur(ind + 1, t.root)
				else:
					return recur(ind + 1, curr.links[ord(A[ind]) - ord('a')])
			else:
				return 0
		return recur(0, t.root)


class Solution:

	def wordBreak(self, s, wordDict):

		class TreeNode:

			def __init__(self):
				self.mp = {}
				self.isEnd = False

		class Trie:

			def __init__(self):
				self.root = TreeNode()
				self.failed = [False] * 301

			def insert(self, word):
				node = self.root
				for ch in word:
					if ch not in node.mp:
						node.mp[ch] = TreeNode()
					node = node.mp[ch]
				node.isEnd = True

		def check(s, i, root, n):
			if i >= n:
				return True
			start = root
			while i < n and s[i] in start.mp:
				start = start.mp[s[i]]
				i += 1
				if start.isEnd:
					if check(s, i, root, n):
						return True
			return False
		t = Trie()
		for i in wordDict:
			t.insert(i)
		return check(s, 0, t.root, len(s))


class Solution:

	def rec(self, s, seti, n, dp, start):
		if start == n:
			return True
		if dp[start] != -1:
			return dp[start]
		string = ''
		ans = False
		for i in range(start, n):
			string += s[i]
			if string in seti:
				ans = ans or self.rec(s, seti, n, dp, i + 1)
				if ans == True:
					dp[start] = ans
					return True
		dp[start] = ans
		return False

	def wordBreak(self, s, wordDict):
		n = len(s)
		seti = set(wordDict)
		dp = [-1] * (n + 1)
		return self.rec(s, seti, n, dp, 0)


class Trie:

	def __init__(self, words=[]):
		self.root = {}
		for word in words:
			self.add(word)

	def add(self, word):
		word += '$'
		curr = self.root
		for c in word:
			if c not in curr:
				curr[c] = {}
			curr = curr[c]

	def isPrefix(self, word):
		word += '$'
		curr = self.root
		for c in word:
			if c not in curr:
				return False
			curr = curr[c]
		return True

class Solution:

	def solve(self, word, n, trie, i, memo):
		if i == n:
			return True
		if i in memo:
			return memo[i]
		for j in range(i + 1, n + 1):
			if trie.isPrefix(word[i:j]) and self.solve(word, n, trie, j, memo):
				memo[i] = True
				return True
		memo[i] = False
		return False

	def wordBreak(self, A, B):
		n = len(A)
		trie = Trie(B)
		memo = {}
		return self.solve(A, n, trie, 0, memo)


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, root, word):

		def util(root, index, word):
			if len(word) == index:
				root.isEndOfWord = True
				return
			char = word[index]
			temp = ord(char) - ord('a')
			if root.children[temp] != None:
				son = root.children[temp]
			else:
				root.children[temp] = TrieNode()
				son = root.children[temp]
			util(son, index + 1, word)
		util(root, 0, word)

class Solution:

	def wordBreak(self, a, d):

		def search(root, word):
			ans = [False]

			def utils(root, index, word):
				if index == len(word):
					if root.isEndOfWord == True:
						ans[0] = True
					return
				ind = ord(word[index]) - ord('a')
				if root.children[ind] != None:
					son = root.children[ind]
				else:
					return
				utils(son, index + 1, word)
			utils(root, 0, word)
			return ans[0]

		def solve(st, root):
			n = len(st)
			if n == 0:
				return True
			for i in range(1, n + 1):
				if search(root, st[:i]) and solve(st[i:], root):
					return True
			return False
		t = Trie()
		root = t.root
		for i in d:
			t.insert(root, i)
		return solve(a, root)


class Trie:

	def __init__(self):
		self.child = [None] * 26
		self.leaf = False

def chartoidx(key):
	return ord(key) - ord('a')

class Solution:

	def wordBreak(self, a, d):
		root = Trie()
		for i in range(len(d)):
			cr = root
			for j in range(len(d[i])):
				index = chartoidx(d[i][j])
				if not cr.child[index]:
					cr.child[index] = Trie()
				cr = cr.child[index]
			cr.leaf = True

		def search(root, a):
			cr = root
			for i in range(len(a)):
				index = chartoidx(a[i])
				if not cr.child[index]:
					return False
				cr = cr.child[index]
			return cr != None and cr.leaf

		def wordbreak(root, st):
			n = len(st)
			if n == 0:
				return True
			for i in range(1, n + 1, 1):
				if search(root, st[0:i]) and wordbreak(root, st[i:]):
					return True
			return False
		cr = root
		return 1 if wordbreak(cr, a) else 0


class Solution:

	def wordBreak(self, a, d):
		dp = {0: True}
		n = len(a)
		for i in range(1, n + 1):
			dp[i] = False
			for j in range(i):
				if dp[j] and a[j:i] in d:
					dp[i] = True
					break
		return dp[n]


import sys
sys.setrecursionlimit(int(1000000.0))

class Node:

	def __init__(self):
		self.mp = [None] * 26
		self.flag = False

class Trie:

	def __init__(self):
		self.root = Node()

	def get(self, node):
		return node.mp

	def add(self, word):
		temp = self.root
		for i in word:
			nxt = self.get(temp)
			if nxt[ord(i) - 97] == None:
				nxt[ord(i) - 97] = Node()
			temp = nxt[ord(i) - 97]
		temp.flag = True

	def search(self, word):
		temp = self.root
		for i in word:
			nxt = self.get(temp)
			if nxt[ord(i) - 97] == None:
				return False
			temp = nxt[ord(i) - 97]
		return temp.flag

class Solution:

	def wordBreak(self, A, B):
		trie = Trie()
		for word in B:
			trie.add(word)
		n = len(A)

		def soln(i):
			if i == n:
				return 1
			if i in dp:
				return dp[i]
			dp[i] = 0
			for k in range(i + 1, n + 1):
				if trie.search(A[i:k]) and soln(k):
					dp[i] = 1
					break
			return dp[i]
		dp = {}
		return soln(0)


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.end = False

class Solution:

	def insert(self, root, key):
		for level in range(len(key)):
			ind = ord(key[level]) - ord('a')
			if not root.children[ind]:
				root.children[ind] = TrieNode()
			root = root.children[ind]
		root.end = True

	def util(self, root, A):
		if A == '':
			return True
		curr = root
		temp = ''
		level = 0
		n = len(A)
		while level < n:
			temp += A[level]
			ind = ord(A[level]) - ord('a')
			if not curr.children[ind]:
				return False
			if curr.children[ind].end:
				if self.util(root, A[level + 1:]):
					return True
			level += 1
			curr = curr.children[ind]
		return False

	def wordBreak(self, A, B):
		root = TrieNode()
		for i in B:
			self.insert(root, i)
		return self.util(root, A)


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isword = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, s):
		curr = self.root
		for ch in s:
			o = ord(ch) - ord('a')
			if curr.children[o] is None:
				curr.children[o] = TrieNode()
			curr = curr.children[o]
		curr.isword = True

	def search(self, s):
		curr = self.root
		for ch in s:
			o = ord(ch) - ord('a')
			if curr.children[o] is None:
				return False
			curr = curr.children[o]
		return curr.isword

def util(A, trie):
	if len(A) == 0:
		return True
	for i in range(1, len(A) + 1):
		if trie.search(A[0:i]) and util(A[i:], trie):
			return True
	return False

class Solution:

	def wordBreak(self, A, B):
		trie = Trie()
		for w in B:
			trie.insert(w)
		return util(A, trie)


from collections import deque

class Solution:

	def wordBreak(self, s, word):
		word_set = set(word)
		q = deque()
		visited = set()
		q.append(0)
		visited.add(0)
		while q:
			start = q.popleft()
			if start == len(s):
				return True
			for end in range(start + 1, len(s) + 1):
				if s[start:end] in word_set and end not in visited:
					q.append(end)
					visited.add(end)
		return False


class Solution:

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


class Solution:

	def wordBreak(self, A, B):
		size = len(A)
		if size == 0:
			return True
		for i in range(1, size + 1):
			if A[0:i] in B and self.wordBreak(A[i:size], B):
				return True
		return False
if __name__ == '__main__':
	test_case = int(input())
	for _ in range(test_case):
		number_of_elements = int(input())
		dictionary = [word for word in input().strip().split()]
		line = input().strip()
		ob = Solution()
		res = ob.wordBreak(line, dictionary)
		if res:
			print(1)
		else:
			print(0)


class Trie:

	def __init__(self, words=[]):
		self.root = {}
		for word in words:
			self.add(word)

	def add(self, word):
		word += '$'
		curr = self.root
		for c in word:
			if c not in curr:
				curr[c] = {}
			curr = curr[c]

	def isPrefix(self, word):
		word += '$'
		curr = self.root
		for c in word:
			if c not in curr:
				return False
			curr = curr[c]
		return True

class Solution:

	def solve(self, word, n, trie, i, memo):
		if i == n:
			return True
		if i in memo:
			return memo[i]
		for j in range(i + 1, n + 1):
			if trie.isPrefix(word[i:j]) and self.solve(word, n, trie, j, memo):
				memo[i] = True
				return True
		memo[i] = False
		return False

	def wordBreak(self, A, B):
		n = len(A)
		trie = Trie(B)
		memo = {}
		return self.solve(A, n, trie, 0, memo)
if __name__ == '__main__':
	test_case = int(input())
	for _ in range(test_case):
		number_of_elements = int(input())
		dictionary = [word for word in input().strip().split()]
		line = input().strip()
		ob = Solution()
		res = ob.wordBreak(line, dictionary)
		if res:
			print(1)
		else:
			print(0)


class TrieNode:

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

class Solution:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word):
		cur = self.root
		for char in word:
			if char not in cur.children:
				cur.children[char] = TrieNode()
			cur = cur.children[char]
		cur.end = True

	def search(self, word):
		cur = self.root
		for char in word:
			if char not in cur.children:
				return False
			cur = cur.children[char]
		return cur.end

	def helper(self, A):
		n = len(A)
		if n == 0:
			return True
		for i in range(1, n + 1):
			if self.search(A[:i]) and self.helper(A[i:]):
				return True
		return False

	def wordBreak(self, A, B):
		for word in B:
			self.insert(word)
		return self.helper(A)
if __name__ == '__main__':
	test_case = int(input())
	for _ in range(test_case):
		number_of_elements = int(input())
		dictionary = [word for word in input().strip().split()]
		line = input().strip()
		ob = Solution()
		res = ob.wordBreak(line, dictionary)
		if res:
			print(1)
		else:
			print(0)


class Solution:

	def wordBreak(self, s, wordDict):
		n = len(s)
		words = set(wordDict)
		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 words:
					dp[i] = True
					break
		return dp[n]
if __name__ == '__main__':
	test_case = int(input())
	for _ in range(test_case):
		number_of_elements = int(input())
		dictionary = [word for word in input().strip().split()]
		line = input().strip()
		ob = Solution()
		res = ob.wordBreak(line, dictionary)
		if res:
			print(1)
		else:
			print(0)


class Node:

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

class Solution:

	def __init__(self):
		self.root = Node()

	def insert(self, word):
		curr = self.root
		for i in word:
			if i in curr.children:
				curr = curr.children[i]
			else:
				new = Node()
				curr.children[i] = new
				curr = curr.children[i]
		curr.end = True

	def isleaf(self, word):
		curr = self.root
		for i in word:
			if i in curr.children:
				curr = curr.children[i]
			else:
				return False
		if curr.end == True:
			return True
		return False

	def check(self, word):
		n = len(word)
		if n == 0:
			return True
		for i in range(1, n + 1):
			if self.isleaf(word[:i]):
				if self.check(word[i:]):
					return True
		return False

	def wordBreak(self, A, B):
		for i in B:
			self.insert(i)
		return self.check(A)
if __name__ == '__main__':
	test_case = int(input())
	for _ in range(test_case):
		number_of_elements = int(input())
		dictionary = [word for word in input().strip().split()]
		line = input().strip()
		ob = Solution()
		res = ob.wordBreak(line, dictionary)
		if res:
			print(1)
		else:
			print(0)


class Solution:

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


class Node:

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

class Solution:

	def __init__(self):
		self.root = Node()

	def insert(self, word):
		curr = self.root
		for i in word:
			if i in curr.children:
				curr = curr.children[i]
			else:
				new = Node()
				curr.children[i] = new
				curr = curr.children[i]
		curr.end = True

	def isLeaf(self, word):
		curr = self.root
		for i in word:
			if i in curr.children:
				curr = curr.children[i]
			else:
				return False
		if curr.end == True:
			return True
		return False

	def check(self, word):
		n = len(word)
		if n == 0:
			return True
		for i in range(1, n + 1):
			if self.isLeaf(word[:i]) and self.check(word[i:]):
				return True
		return False

	def wordBreak(self, A, B):
		for i in B:
			self.insert(i)
		if self.check(A):
			return True
		return False


class Solution:

	def wordBreak(self, s, d):
		d1 = {}

		def match(word, d, n):
			if word == '':
				return True
			for i in range(n + 1):
				if word[0:i] in d:
					if word[i:] not in d1:
						if match(word[i:], d, len(word[i:])):
							d1[word[i:]] = True
							return True
					else:
						return d1[word[i:]]
		return match(s, d, len(line))


class Solution:

	def wordBreak(self, s, words):

		class trie:

			def __init__(self):
				self.children = [None] * 26
				self.eow = False

		def insert(root, key):
			for i in key:
				ind = ord(i) - ord('a')
				if not root.children[ind]:
					root.children[ind] = trie()
				root = root.children[ind]
			root.eow = True

		def search(root, key):
			for i in key:
				ind = ord(i) - ord('a')
				if not root.children[ind]:
					return False
				root = root.children[ind]
			if root.eow:
				return True
			return False
		root = trie()
		for i in words:
			insert(root, i)

		def check(root, s):
			if len(s) == 0:
				return True
			for i in range(1, len(s) + 1):
				if search(root, s[:i]) and check(root, s[i:]):
					return True
			return False
		return check(root, s)


class Solution:

	def wordBreak(self, A, B):
		d = {}
		cache = {}
		for i in B:
			d[i] = i

		def rec(word, i):
			if i >= len(word):
				return True
			if i in cache:
				return cache[i]
			for j in range(i, len(word)):
				if word[i:j + 1] in d:
					if rec(word, j + 1):
						cache[i] = True
						return True
			cache[i] = False
			return cache[i]
		return rec(A, 0)


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.wordCount = 0
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl.wordCount += 1
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		if key == '':
			return True
		pCrawl = self.root
		length = len(key)
		i = 0
		for level in range(length):
			index = self._charToIndex(key[level])
			if pCrawl.isEndOfWord and self.search(key[i:]):
				return True
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
			i += 1
		if pCrawl.isEndOfWord:
			return True
		return False

class Solution:

	def wordBreak(self, A, B):
		t = Trie()
		for key in B:
			t.insert(key)
		result = t.search(A)
		return 1 if result else 0


class Solution:

	def wordBreak(self, A, B):
		if len(A) == 0:
			return 1
		for word in B:
			if len(word) > len(A):
				continue
			if A[0:len(word)] == word:
				if self.wordBreak(A[len(word):], B):
					return 1
		return 0


class TrieNode:

	def __init__(self):
		self.children = dict()
		self.isLeaf = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, key):
		current = self.root
		for char in key:
			if char not in current.children:
				current.children[char] = TrieNode()
			current = current.children[char]
		current.isLeaf = True

	def search(self, word):
		current = self.root
		for i in range(len(word)):
			if word[i] not in current.children:
				return False
			current = current.children[word[i]]
		return current.isLeaf

class Solution:

	def _wordBreak(self, A, trie, start):
		if start == len(A):
			return 1
		temp = ''
		for i in range(start, len(A)):
			temp += A[i]
			if trie.search(temp) and self._wordBreak(A, trie, i + 1):
				return 1
		return 0

	def wordBreak(self, A, B):
		trie = Trie()
		for word in B:
			trie.insert(word)
		return self._wordBreak(A, trie, 0)


class TrieNode:

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

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word):
		cur = self.root
		for i in word:
			if i not in cur.children:
				cur.children[i] = TrieNode()
			cur = cur.children[i]
		cur.endofword = True

	def search(self, word):
		cur = self.root
		for i in word:
			if i not in cur.children:
				return False
			cur = cur.children[i]
		return cur.endofword

	def check(self, word):
		cur = self.root
		if len(word) == 0:
			return True
		for i in range(1, len(word) + 1):
			if self.search(word[:i]) and self.check(word[i:]):
				return True
		return False

class Solution:

	def wordBreak(self, A, B):
		trie = Trie()
		for i in B:
			trie.insert(i)
		res = trie.check(A)
		if res:
			return 1
		return 0


class Solution:

	def wordBreak(self, s, l):
		n = len(s)
		dp = [0 for _ in range(n + 1)]
		dp[-1] = 1
		for i in range(n - 1, -1, -1):
			for x in l:
				if i + len(x) <= n and s[i:i + len(x)] == x:
					dp[i] = dp[i + len(x)]
				if dp[i]:
					break
		return dp[0]


class Solution:

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


class Solution:

	def wordBreak(self, A, B):
		d = set(B)
		dp = [True]
		for i in range(1, len(A) + 1):
			res = False
			for j in range(i):
				res = res or (dp[j] and A[j:i] in d)
			dp.append(res)
		return 1 if dp[-1] else 0


class Solution:

	def wordBreak(self, a, b):

		def wb(word):
			global dictionary
			size = len(word)
			if size == 0:
				return True
			for i in range(1, size + 1):
				if word[0:i] in dictionary and wb(word[i:size]):
					return True
			return False
		dictionary = set()
		temp_dictionary = b
		for temp in temp_dictionary:
			dictionary.add(temp)
		return True if wb(a) else False


class Node:

	def __init__(self):
		self.chi = {}
		self.isla = False

class trie:

	def __init__(self):
		self.root = Node()

	def add(self, word):
		t = self.root
		for val in word:
			if t.chi.get(val) is None:
				t.chi[val] = Node()
			t = t.chi[val]
		t.isla = True

	def find(self, s, i, n, ans):
		t = self.root
		for j in range(i, n):
			if t.chi.get(s[j]) is None:
				return
			t = t.chi[s[j]]
			if t.isla:
				ans[i] |= ans[j + 1]

class Solution:

	def wordBreak(self, s, arr):
		tr = trie()
		for val in arr:
			tr.add(val)
		n = len(s)
		ans = [False for i in range(n + 1)]
		ans[-1] = True
		for i in range(n - 1, -1, -1):
			tr.find(s, i, n, ans)
		return ans[0]


class Solution:

	def wordBreak(self, A, B):
		tree = to_tree(dictionary)
		return check(line, tree)

class Tree:

	def __init__(self, letter):
		self.letter = letter
		self.is_word = False
		self.children = {}

	def add(self, letter):
		if letter not in self.children:
			self.children[letter] = Tree(letter)
		return self.children[letter]

def check(line, tree):
	if line == '':
		return True
	pos = tree
	for (i, c) in enumerate(line):
		if c not in pos.children:
			return False
		pos = pos.children[c]
		if pos.is_word:
			if check(line[i + 1:], tree):
				return True
	return False

def to_tree(dic):
	tree = Tree(None)
	for word in dic:
		prev = tree
		for c in word:
			prev = prev.add(c)
		prev.is_word = True
	return tree


class Node:

	def __init__(self):
		self.child = [None] * 26
		self.is_end = False

class Trie:

	def __init__(self):
		self.root = Node()

	def getindex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		node = self.root
		for letter in key:
			ind = self.getindex(letter)
			if not node.child[ind]:
				node.child[ind] = Node()
			node = node.child[ind]
		node.is_end = True

	def search(self, key):
		node = self.root
		counter = 0
		for letter in key:
			ind = self.getindex(letter)
			if not node.child[ind]:
				return False
			node = node.child[ind]
			counter += 1
		return node and node.is_end

	def search_exist(self, key):
		(prev_counter, updated_counter) = (0, 0)
		length_key = len(key)
		if length_key == 0:
			return True
		for i in range(1, length_key + 1):
			if self.search(key[:i]) and self.search_exist(key[i:]):
				return True
		return False

class Solution:

	def wordBreak(self, A, B):
		trie_obj = Trie()
		for i in B:
			trie_obj.insert(i)
		return trie_obj.search_exist(A)


class Solution:

	def wordBreak(self, s, x):

		def f(i):
			if i >= l:
				return True
			if i in dp:
				return dp[i]
			ans = False
			for j in range(i, l):
				q = s[i:j + 1]
				if q in x:
					ans = ans or f(j + 1)
					if ans:
						break
			dp[i] = ans
			return ans
		x = set(x)
		dp = {}
		l = len(s)
		return f(0)


from functools import lru_cache

class Solution:

	def wordBreak(self, A, B):
		B = set(B)
		n = len(A)

		@lru_cache(None)
		def solve(idx, path):
			if idx == n:
				return True if path in B else False
			ans = False
			for i in range(idx, n):
				path += A[i]
				if path in B:
					ans = ans or solve(i + 1, '')
				ans = ans or solve(i + 1, path)
				if ans:
					return ans
			return ans
		return 1 if solve(0, '') else 0