Given two Lists of strings s1 and s2, you have to count the number of strings in s2 which is either a suffix or prefix of at least one string of s1.
Example 1:
Input:
s1 = ["cat", "catanddog", "lion"]
s2 = ["cat", "dog", "rat"]
Output: 
2
Explanation: 
String "cat" of s2 is prefix of "catanddog"
& string "dog" of s2 is suffix of "catanddog" 
Example 2:
Input: 
s1 = ["jrjiml", "tchetn", "ucrhye", "ynayhy", 
       "cuhffd", "cvgpoiu", "znyadv"]
s2 = ["jr", "ml", "cvgpoi", "gpoiu", "wnmkmluc", 
      "geheqe", "uglxagyl", "uyxdroj"] 
Output: 
4
Explanation: 
String "jr" of s2 is prefix of "jrjiml", 
"ml" of s2 is suffix of "jrjiml", 
"cvgpoi" of s2 is prefix of "cvgpoiu" &
"gpoiu" of s2 is suffix of "cvgpoiu"
Your Task:
You don't need to read input or print anything. Your task is to complete the function prefixSuffixString(), which takes 2 strings s1 and s2 as input and returns an integer value as the number of strings in s2 which is a prefix or suffix in s1.
Expected Time Complexity: O(max(len(s1) , len(s2) ))
Expected Space Complexity: O(1)
Constraints:
   1 <= s1,s2 < 5 * 10^3
   5 <= len(s1[i]), len(s2[i]) < 25

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(max(len(s1) , len(s2) ))
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def prefixSuffixString(self, s1, s2) -> int:

        #code here

Solutions:
class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		ans = 0
		i = 0
		j = 0
		m = len(s1)
		n = len(s2)
		while i < m and j < n:
			if s2[j] in s1[i]:
				l = len(s2[j])
				if s2[j] == s1[i][:l] or s2[j] == s1[i][-l:]:
					ans += 1
					i = 0
					j += 1
				else:
					i += 1
			else:
				i += 1
		return ans


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		dot = '.'
		count = 0
		for string in s1:
			dot += string
			dot += '.'
		for string in s2:
			prefix = '.' + string
			suffix = string + '.'
			if prefix in dot or suffix in dot:
				count += 1
		return count


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		c = 0
		search = set()
		for x in s1:
			for i in range(len(x)):
				search.add(x[i:])
				search.add(x[:i + 1])
		count = 0
		for y in s2:
			if y in search:
				c = c + 1
		return c


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		prefixes_suffixes = set()
		for str1 in s1:
			for i in range(len(str1)):
				prefixes_suffixes.add(str1[:i + 1])
				prefixes_suffixes.add(str1[i:])
		count = 0
		for str2 in s2:
			if str2 in prefixes_suffixes:
				count += 1
		return count


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		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
		for level in range(len(key)):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		for level in range(len(key)):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return True

	def haschild(self, node):
		for i in range(26):
			if node.children[i]:
				return True
		return False

	def displayUtil(self, visited, node, str):
		index = 0
		while index < 26:
			if node.children[index]:
				str += chr(97 + index)
				if node.children[index].isEndOfWord == False:
					self.displayUtil(visited, node.children[index], str)
					str = str[0:len(str) - 1]
				else:
					if str not in visited:
						visited.append(str)
					if self.haschild(node.children[index]):
						self.displayUtil(visited, node.children[index], str)
						str = str[0:len(str) - 1]
			index += 1

	def display(self):
		visited = []
		str = ''
		self.displayUtil(visited, self.root, str)
		print('Content of Trie:')
		for i in range(len(visited)):
			print(visited[i])

class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		t = Trie()
		for str1 in s1:
			t.insert(str1)
			revString = str1[::-1]
			t.insert(revString)
		count = 0
		for str2 in s2:
			revString2 = str2[::-1]
			if t.search(str2) == True or t.search(revString2) == True:
				count += 1
		return count


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		s = set(s1)
		count = 0
		for w in s1:
			for i in range(1, len(w)):
				s.add(w[i:])
				s.add(w[:-i])
		for w in s2:
			if w in s:
				count += 1
		return count


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		from bisect import bisect

		def prefixString(arr, s):
			idx = bisect(arr, s)
			return idx < len(arr) and arr[bisect(arr, s)][:len(s)] == s
		counter = 0
		s1_prefix = sorted(s1)
		s1_suffix = sorted([s[::-1] for s in s1])
		for s_2 in s2:
			counter += prefixString(s1_prefix, s_2) or prefixString(s1_suffix, s_2[::-1])
		return counter


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		c = 0
		i = 0
		j = 0
		while i < len(s1) and j < len(s2):
			if s2[j] == s1[i][:len(s2[j])] or s2[j] == s1[i][len(s1[i]) - len(s2[j]):]:
				c = c + 1
				j = j + 1
				i == 0
			else:
				i = i + 1
		return c


import collections

class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		hm = collections.defaultdict(lambda : False)
		for i in range(len(s1)):
			temp = ''
			for j in range(len(s1[i])):
				temp += s1[i][j]
				hm[temp] = True
			temp = ''
			for j in range(len(s1[i]) - 1, -1, -1):
				temp = s1[i][j] + temp
				hm[temp] = True
		ans = 0
		for i in range(len(s2)):
			if hm[s2[i]] == True:
				ans += 1
		return ans


class TrieNode:

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

class Trie:

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

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

	def check(self, word):
		cur = self.root
		for c in word:
			if c not in cur.children:
				return False
			cur = cur.children[c]
		return True

class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		trie = Trie()
		for s in s1:
			trie.insert(s)
			trie.insert(s[::-1])
		count = 0
		for s in s2:
			if trie.check(s) or trie.check(s[::-1]):
				count += 1
		return count


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		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 = pCrawl.children[index]
		pCrawl.isEndOfWord = True

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

def reverse(s):
	str = ''
	for i in s:
		str = i + str
	return str

class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		tr = Trie()
		for s in s1:
			tr.insert(s)
			tr.insert(reverse(s))
		c = 0
		for s in s2:
			if tr.search(s) or tr.search(reverse(s)):
				c += 1
		return c


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		st = '.'
		for string in s1:
			st += string
			st += '.'
		count = 0
		for el in s2:
			pref = '.' + el
			suff = el + '.'
			if pref in st or suff in st:
				count += 1
		return count


class trieNode:

	def __init__(self):
		self.char = [None] * 26

class Trie:

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

	def insert(self, a):
		curr = self.root
		for el in a:
			if curr.char[ord(el) - ord('a')] == None:
				curr.char[ord(el) - ord('a')] = trieNode()
			curr = curr.char[ord(el) - ord('a')]

	def find(self, a):
		curr = self.root
		for el in a:
			if curr.char[ord(el) - ord('a')] is None:
				return 0
			curr = curr.char[ord(el) - ord('a')]
		return 1

class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		p = Trie()
		for el in s1:
			p.insert(el)
			p.insert(el[::-1])
		ans = 0
		for el in s2:
			if p.find(el) or p.find(el[::-1]):
				ans += 1
		return ans


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		d = set()
		for i in s1:
			k = ''
			l = ''
			p = i[::-1]
			for j in range(len(i)):
				k += i[j]
				l += p[j]
				m = l[::-1]
				d.add(m)
				d.add(k)
		ans = 0
		for i in s2:
			if i in d:
				ans += 1
		return ans


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		ans = 0
		for word in s2:
			for string in s1:
				if word in string:
					if word == string[:len(word)] or word == string[-len(word):]:
						ans += 1
						break
		return ans


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		cnt = 0
		for word1 in s2:
			for word2 in s1:
				if word1 in word2:
					if word1 == word2 or word1 == word2[0:len(word1)] or word1 == word2[-len(word1):]:
						cnt = cnt + 1
						break
		return cnt


class Node:

	def __init__(self):
		self.nod = dict()

class Trie:

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

	def insert(self, val):
		tem = self.root
		for i in val:
			if i not in tem.nod:
				tem.nod[i] = Node()
			tem = tem.nod[i]

	def search(self, val):
		tem = self.root
		for i in val:
			if i not in tem.nod:
				return False
			tem = tem.nod[i]
		return True

class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		ans = 0
		i = 0
		j = 0
		m = len(s1)
		n = len(s2)
		while i < m and j < n:
			if s2[j] in s1[i]:
				l = len(s2[j])
				if s2[j] == s1[i][:l] or s2[j] == s1[i][-l:]:
					ans += 1
					i = 0
					j += 1
				else:
					i += 1
			else:
				i += 1
		return ans


class Solution:

	class TrieNode:

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

		def insert(self, s1, root):
			cur = root
			for i in range(0, len(s1)):
				index = ord(s1[i]) - ord('a')
				if cur.children[index] is None:
					cur.children[index] = Solution.TrieNode()
				cur = cur.children[index]
			cur.isEndOfWord = True

		def search(self, s1, root):
			cur = root
			for i in range(0, len(s1)):
				index = ord(s1[i]) - ord('a')
				if cur.children[index] is None:
					return False
				cur = cur.children[index]
			return True

	def prefixSuffixString(self, s1, s2) -> int:
		root = self.TrieNode()
		for val in s1:
			root.insert(val[::-1], root)
			root.insert(val, root)
		ans = 0
		for val in s2:
			if root.search(val, root) or root.search(val[::-1], root):
				ans += 1
		return ans


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		prefixes = set((s[:i] for s in s1 for i in range(1, len(s) + 1)))
		suffixes = set((s[i:] for s in s1 for i in range(len(s))))
		count = 0
		for s in s2:
			if s in prefixes or s in suffixes:
				count += 1
		return count


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		prefixes = set()
		suffixes = set()
		for i in s1:
			for j in range(1, len(i)):
				prefixes.add(i[:j])
				suffixes.add(i[-j:])
		x = 0
		for j in s2:
			if j in prefixes or j in suffixes:
				x += 1
		return x


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:

		def insert(dic, string, n, i=0):
			if i == n:
				return
			if dic == None:
				dic = {}
			if string[i] in dic:
				dic[string[i]] = insert(dic[string[i]], string, n, i + 1)
			else:
				dic[string[i]] = None
				dic[string[i]] = insert(dic[string[i]], string, n, i + 1)
			return dic


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		hshset = set(s1)
		for w in s1:
			for i in range(1, len(w)):
				hshset.add(w[:i])
				hshset.add(w[-i:])
		return sum((w in hshset for w in s2))


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		i = 0
		j = 0
		count = 0
		n = len(s1)
		n1 = len(s2)
		while j < n1 and i < n:
			if s2[j] in s1[i]:
				l = len(s2[j])
				if s1[i][:l] == s2[j] or s1[i][-l:] == s2[j]:
					count += 1
					i = 0
					j += 1
				else:
					i += 1
			else:
				i += 1
		return count


class Node:

	def __init__(self):
		self.nod = dict()

class Trie:

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

	def insert(self, val):
		tem = self.root
		for i in val:
			if i not in tem.nod:
				tem.nod[i] = Node()
			tem = tem.nod[i]

	def search(self, val):
		tem = self.root
		for i in val:
			if i not in tem.nod:
				return False
			tem = tem.nod[i]
		return True

class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		root1 = Trie()
		root2 = Trie()
		for word in s1:
			root1.insert(word)
			root2.insert(word[::-1])
		ans = 0
		for word in s2:
			if root1.search(word) or root2.search(word[::-1]):
				ans += 1
		return ans


class Solution:

	def check_prefix(self, s):
		for i in range(len(s1)):
			if s in s1[i]:
				if s1[i][:len(s)] == s or s1[i][len(s1[i]) - len(s):] == s:
					return True
			else:
				continue

	def prefixSuffixString(self, s1, s2) -> int:
		c = 0
		for i in s2:
			if self.check_prefix(i):
				c += 1
		return c


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		count = 0
		for i in s2:
			x = len(i)
			for j in s1:
				if i in j:
					y = j[0:x]
					z = j[-x:]
					if i == y or i == z:
						count += 1
						break
					else:
						continue
				else:
					continue
		return count


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		(p, q) = (0, 0)
		res = 0
		x = len(s1)
		y = len(s2)
		while p < x and q < y:
			if s2[q] in s1[p]:
				a = len(s2[q])
				if s2[q] == s1[p][:a] or s2[q] == s1[p][-a:]:
					res += 1
					p = 0
					q += 1
				else:
					p += 1
			else:
				p += 1
		return res


class TrieNode(object):

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

class Trie(object):

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

	def insert(self, l):
		currnode = self.root
		for c in l:
			if c not in currnode.children:
				currnode.children[c] = TrieNode()
			currnode = currnode.children[c]
		currnode.end_of_word = True

	def search(self, l):
		currnode = self.root
		for c in l:
			if c not in currnode.children:
				currnode.children[c] = TrieNode()
			currnode = currnode.children[c]
		return currnode.end_of_word

	def search(self, l):
		currnode = self.root
		for c in l:
			if c not in currnode.children:
				return False
			currnode = currnode.children[c]
		return True

class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		t = Trie()
		count = 0
		for s in s1:
			sl = list(s)
			t.insert(sl)
			sl.reverse()
			t.insert(sl)
		for s in s2:
			sl = list(s)
			if t.search(sl):
				count = count + 1
			else:
				sl.reverse()
				if t.search(sl):
					count = count + 1
		return count


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		cnt = 0
		for i in s2:
			for j in s1:
				if i in j and i != j and (j[0] == i[0] or j[-1] == i[-1]):
					cnt += 1
					break
		return cnt


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		count = 0
		for ele2 in s2:
			for ele1 in s1:
				if ele2 in ele1 and (ele1[:len(ele2)] == ele2 or ele1[-1 * len(ele2):] == ele2):
					count += 1
					break
		return count


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		cnt = 0
		for i in s2:
			l = len(i)
			for j in s1:
				if i[0] == j[0]:
					if i == j[:l]:
						cnt += 1
						break
				if i[-1] == j[-1]:
					if i == j[-l:]:
						cnt += 1
						break
		return cnt


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		counter = {}
		for i in s1:
			for j in range(1, len(i)):
				counter[i[:j]] = 1
				counter[i[-j:]] = 1
		ans = 0
		for i in s2:
			if i in counter.keys():
				ans += 1
		return ans


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		prefix = set()
		suffix = set()
		for i in s1:
			for j in range(len(i)):
				prefix.add(i[:j + 1])
				suffix.add(i[j:])
		total = 0
		for s in s2:
			if s in prefix or s in suffix:
				total += 1
		return total


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		y = set(s1)
		for x in s1:
			for i in range(1, len(x)):
				y.add(x[:i])
				y.add(x[-i:])
		return sum((x in y for x in s2))


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		mm = {}
		for x in s1:
			temp = ''
			for i in range(len(x)):
				temp += x[i]
				mm[temp] = True
			temp = ''
			for i in range(len(x) - 1, -1, -1):
				temp = x[i] + temp
				mm[temp] = True
		ans = 0
		for x in s2:
			if x in mm:
				ans += 1
		return ans


class Trie:

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

class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		trie = Trie()

		def insert(word):
			root = trie
			for i in word:
				if i not in root.child:
					root.child[i] = Trie()
				root = root.child[i]
			root.isend = True

		def search(word):
			root = trie
			for i in word:
				if i not in root.child:
					return False
				root = root.child[i]
			return True
		for i in s1:
			insert(i)
			insert(i[::-1])
		ans = 0
		for i in s2:
			if search(i) or search(i[::-1]):
				ans += 1
		return ans


class Solution:

	def prefixSuffixString(self, s1, s2) -> int:
		s = set(s1)
		for a in s1:
			for i in range(1, len(a)):
				s.add(a[:i])
				s.add(a[-i:])
		return sum((1 for a in s2 if a in s))


class Solution:

	def prefix(self, x, y):
		j = 0
		if len(x) < len(y):
			for k in range(len(x)):
				if x[k] == y[j]:
					j += 1
				else:
					return 0
			return 1
		else:
			for k in range(len(y)):
				if y[k] == x[j]:
					j += 1
				else:
					return 0
			return 1

	def suffix(self, x, y):
		i = len(x)
		j = len(y)
		if i < j:
			for k in range(i - 1, -1, -1):
				if x[k] == y[j - 1]:
					j -= 1
				else:
					return 0
			return 1
		else:
			for k in range(j - 1, -1, -1):
				if y[k] == x[i - 1]:
					i -= 1
				else:
					return 0
			return 1

	def prefixSuffixString(self, s1, s2) -> int:
		j = c = 0
		for s in s2:
			while j < len(s1):
				if self.prefix(s, s1[j]) or self.suffix(s, s1[j]):
					c += 1
					break
				else:
					j += 1
		return c