Penelope and her classmates are lost in the Forbidden Forest and the Devil is out to get them. But Penelope has magical powers that can build bridges across the dangerous river and take her friends to safety. The only bridges that can withstand the Devil's wrath are the ones built between two similar trees in the forest. 
Given str1 and str2 denoting the order of trees on either side of the river, find the maximum number of bridges that Penelope can build and save everyone from the Devil. 
Note: Each tree in the forest belongs to one of the 3 categories represented by * or # or @, and it's easy to understand that bridges do not intersect or cross each other. 
Example 1:
Input:
str1 = "*@#*" 
str2 = "*#"
Output:
2
Explanation:
str1 = "*@#*" and str2 = "*#" 
Two bridges can be built between the banks 
of the river in the following manner. 
* @ # *
|   |
*   #
Example 2:
Input:
str1 = "***"
str2 = "##"
Output:
0
Your Task:
You don't need to read input or print anything. Complete the function build_bridges() that takes str1 and str2 as input parameters and returns the maximum number of bridges that can be built. 
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(N*M)
Constraints:
1 ≤ N, M ≤ 100
Where, N and M are the size of the string str1 and str2 respectively.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: class Solution:

    def build_bridges(self, str1, str2):

        # code here



Solutions:
class Solution:

	def build_bridges(self, str1, str2):
		dp = [[0 for i in range(len(str2) + 1)] for j in range(len(str1) + 1)]
		for i in range(len(str1) + 1):
			for j in range(len(str2) + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif str1[i - 1] == str2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[len(str1)][len(str2)]


class Solution:

	def build_bridges(self, s1, s2):
		n = len(s1)
		m = len(s2)
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i][j - 1])
		return dp[n][m]


class Solution:

	def build_bridges(self, str1, str2):
		return self.helper(str1, str2, {})

	def helper(self, s1, s2, store):
		if not s1 or not s2:
			return 0
		if (s1, s2) in store:
			return store[s1, s2]
		if s1[0] == s2[0]:
			store[s1, s2] = self.helper(s1[1:], s2[1:], store) + 1
			return store[s1, s2]
		first = self.helper(s1[1:], s2, store)
		second = self.helper(s1, s2[1:], store)
		store[s1, s2] = max(first, second)
		return store[s1, s2]


class Solution:

	def build_bridges(self, str1, str2):
		m = len(str1)
		n = len(str2)
		sub = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(m - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				if str1[i] == str2[j]:
					sub[i][j] = 1 + sub[i + 1][j + 1]
				else:
					sub[i][j] = max(sub[i + 1][j], sub[i][j + 1])
		return sub[0][0]


class Solution:

	def build_bridges(self, text1, text2):
		(len1, len2) = (len(text1), len(text2))
		dp = [[0 for i in range(len2)] for i in range(len1)]
		for i in range(len1):
			for j in range(len2):
				if text1[i] == text2[j]:
					if i == 0 or j == 0:
						dp[i][j] = 1
					else:
						dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[-1][-1]


class Solution:

	def build_bridges(self, str1, str2):
		N = len(str1)
		M = len(str2)
		dp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(1, M + 1):
				if str1[i - 1] == str2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[N][M]


def f(A, B, i, j, N, M, dp):
	if i == N or j == M:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	ans = 0
	if A[i] == B[j]:
		ans = 1 + f(A, B, i + 1, j + 1, N, M, dp)
	else:
		ans = max(f(A, B, i + 1, j, N, M, dp), f(A, B, i, j + 1, N, M, dp))
	dp[i][j] = ans
	return ans

class Solution:

	def build_bridges(self, A, B):
		N = len(A)
		M = len(B)
		dp = [[-1 for i in range(M)] for i in range(N)]
		ans = f(A, B, 0, 0, N, M, dp)
		return ans


class Solution:

	def build_bridges(self, s1, s2):
		n = len(s1)
		m = len(s2)
		dp = [[0] * (m + 1) for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if i == 0 or j == 0:
					continue
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		return dp[n][m]
if __name__ == '__main__':
	T = int(input())
	for _ in range(T):
		obj = Solution()
		(str1, str2) = input().split()
		print(obj.build_bridges(str1, str2))


class Solution:

	def lcs(self, str1, str2, n1, n2):
		if n1 == 0 or n2 == 0:
			return 0
		elif str1[n1 - 1] == str2[n2 - 1]:
			return 1 + self.lcs(str1, str2, n1 - 1, n2 - 1)
		else:
			return max(self.lcs(str1, str2, n1, n2 - 1), self.lcs(str1, str2, n1 - 1, n2))

	def build_bridges(self, str1, str2):
		dp = [[0] * len(str2) for i in range(len(str1))]
		for i in range(len(str1)):
			for j in range(len(str2)):
				if str1[i] == str2[j]:
					if i == 0 or j == 0:
						dp[i][j] = 1
					else:
						dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[-1][-1]
if __name__ == '__main__':
	T = int(input())
	for _ in range(T):
		obj = Solution()
		(str1, str2) = input().split()
		print(obj.build_bridges(str1, str2))


class Solution:

	def build_bridges(self, str1, str2):
		dp = [[-1 for x in range(len(str1) + 1)] for y in range(len(str2) + 1)]
		for x in range(len(dp) - 1, -1, -1):
			for y in range(len(dp[x]) - 1, -1, -1):
				if x == len(dp) - 1 or y == len(dp[x]) - 1:
					dp[x][y] = 0
				elif str1[y] == str2[x]:
					dp[x][y] = dp[x + 1][y + 1] + 1
				else:
					dp[x][y] = max(dp[x + 1][y], dp[x][y + 1])
		return dp[0][0]
if __name__ == '__main__':
	T = int(input())
	for _ in range(T):
		obj = Solution()
		(str1, str2) = input().split()
		print(obj.build_bridges(str1, str2))


class Solution:

	def build_bridges(self, str1, str2):
		A = str1
		B = str2
		m = len(A)
		n = len(B)
		dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if A[i - 1] == B[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[m][n]


class Solution:

	def build_bridges(self, str1, str2):
		n = len(str1)
		m = len(str2)
		F = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if j == 0 or i == 0:
					F[i][j] = 0
				elif str1[j - 1] == str2[i - 1]:
					F[i][j] = F[i - 1][j - 1] + 1
				else:
					F[i][j] = max(F[i - 1][j], F[i][j - 1])
		return F[m][n]


class Solution:

	def build_bridges(self, str1, str2):
		n1 = len(str1)
		n2 = len(str2)
		dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				if str1[i - 1] == str2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[n1][n2]


class Solution:

	def build_bridges(self, str1, str2):
		d = [[0] * (len(str2) + 1) for i in range(len(str1) + 1)]
		for i in range(1, len(str1) + 1):
			for j in range(1, len(str2) + 1):
				if str1[i - 1] == str2[j - 1]:
					d[i][j] = 1 + d[i - 1][j - 1]
				else:
					d[i][j] = max(d[i - 1][j], d[i][j - 1])
		return d[-1][-1]


class Solution:

	def build_bridges(self, str1, str2):
		memo = [[0 for _ in range(len(str2) + 1)] for _ in range(len(str1) + 1)]
		for i in range(len(str1)):
			for j in range(len(str2)):
				memo[i + 1][j] = max(memo[i + 1][j], memo[i][j])
				memo[i][j + 1] = max(memo[i][j + 1], memo[i][j])
				if str1[i] == str2[j]:
					memo[i + 1][j + 1] = max(memo[i + 1][j + 1], memo[i][j] + 1)
		return max(max(memo[-1]), max((r[-1] for r in memo)))


class Solution:

	def build_bridges(self, X, Y):
		m = len(X)
		n = len(Y)
		L = [[None] * (n + 1) for i in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					L[i][j] = 0
				elif X[i - 1] == Y[j - 1]:
					L[i][j] = L[i - 1][j - 1] + 1
				else:
					L[i][j] = max(L[i - 1][j], L[i][j - 1])
		return L[m][n]


class Solution:

	def build_bridges(self, x, y):
		l = []
		s1 = len(x)
		s2 = len(y)
		for i in range(0, s1 + 1):
			a = []
			for j in range(0, s2 + 1):
				a.append(0)
			l.append(a)
		for i in range(0, s1 + 1):
			for j in range(0, s2 + 1):
				if i == 0 or j == 0:
					l[i][j] = 0
				elif x[i - 1] == y[j - 1]:
					l[i][j] = l[i - 1][j - 1] + 1
				else:
					l[i][j] = max(l[i][j - 1], l[i - 1][j])
		return l[s1][s2]


from functools import lru_cache

class Solution:

	def build_bridges(self, s1, s2):

		@lru_cache(None)
		def lcs(i, j):
			if i >= len(s1) or j >= len(s2):
				return 0
			if s1[i] == s2[j]:
				return 1 + lcs(i + 1, j + 1)
			else:
				return max(lcs(i + 1, j), lcs(i, j + 1))
		return lcs(0, 0)


class Solution:
	dp = []

	def build_bridges(self, str1, str2):
		l1 = len(str1)
		l2 = len(str2)
		Solution.dp = [[-1 for i in range(l2)] for j in range(l1)]
		res = Solution.bridges(l1 - 1, l2 - 1, str1, str2)
		return res

	def bridges(n, m, s1, s2):
		if n < 0 or m < 0:
			return 0
		if (n == 0 or m == 0) and s1[n] == s2[m]:
			return 1
		if Solution.dp[n][m] == -1:
			if s1[n] == s2[m]:
				Solution.dp[n - 1][m - 1] = Solution.bridges(n - 1, m - 1, s1, s2)
				return 1 + Solution.dp[n - 1][m - 1]
			else:
				Solution.dp[n][m] = max(Solution.bridges(n - 1, m, s1, s2), Solution.bridges(n, m - 1, s1, s2))
				return Solution.dp[n][m]
		else:
			return Solution.dp[n][m]


class Solution:

	def build_bridges(self, str1, str2):
		m = len(str1)
		n = len(str2)
		L = [[None] * (n + 1) for i in range(m + 1)]
		count = 0
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					L[i][j] = 0
				elif str1[i - 1] == str2[j - 1]:
					L[i][j] = L[i - 1][j - 1] + 1
				else:
					L[i][j] = max(L[i - 1][j], L[i][j - 1])
		return L[m][n]


class Solution:

	def solve(self, n, m):
		mat = [[0 for i in range(m + 1)] for j in range(n + 1)]
		return mat

	def build_bridges(self, str1, str2):
		n = len(str1)
		m = len(str2)
		mat = self.solve(n, m)
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if str1[i - 1] == str2[j - 1]:
					mat[i][j] = 1 + mat[i - 1][j - 1]
				else:
					mat[i][j] = max(mat[i][j - 1], mat[i - 1][j])
		if n == 0 or m == 0:
			return 0
		else:
			return mat[n][m]


class Solution:

	def build_bridges(self, str1, str2):
		n1 = len(str1)
		n2 = len(str2)
		i = 1
		j = 1
		arr = [[0 for j in range(n2 + 1)] for i in range(n1 + 1)]
		while i <= n1:
			j = 1
			while j <= n2:
				if str1[i - 1] == str2[j - 1]:
					arr[i][j] = 1 + arr[i - 1][j - 1]
				else:
					arr[i][j] = max(arr[i - 1][j], arr[i][j - 1])
				j += 1
			i += 1
		return arr[n1][n2]


class Solution:

	def build_bridges(self, str1, str2):
		dp = []
		for i in range(len(str1)):
			dp.append([-1 for _ in range(len(str2))])

		def lcs(i, j, c1, c2):
			nonlocal dp
			if i == len(c1) or j == len(c2):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if c1[i] == c2[j]:
				return 1 + lcs(i + 1, j + 1, c1, c2)
			else:
				dp[i][j] = max(lcs(i + 1, j, c1, c2), lcs(i, j + 1, c1, c2))
				return dp[i][j]
		return lcs(0, 0, str1, str2)


from collections import Counter

class Solution:

	def build_bridges_util(self, str1, str2, i, j, dp):
		if i >= len(str1) or j >= len(str2):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if str1[i] == str2[j]:
			dp[i][j] = 1 + self.build_bridges_util(str1, str2, i + 1, j + 1, dp)
			return dp[i][j]
		dp[i][j] = max(self.build_bridges_util(str1, str2, i + 1, j, dp), self.build_bridges_util(str1, str2, i, j + 1, dp))
		return dp[i][j]

	def build_bridges(self, str1, str2):
		(n1, n2) = (len(str1), len(str2))
		dp = [[-1 for i in range(n2 + 1)] for j in range(n1 + 1)]
		return self.build_bridges_util(str1, str2, 0, 0, dp)


class Solution:

	def build_bridges(self, text1, text2):
		matrix = [[0 for j in range(len(text2) + 1)] for i in range(len(text1) + 1)]
		for i in range(len(text1) - 1, -1, -1):
			for j in range(len(text2) - 1, -1, -1):
				if text1[i] == text2[j]:
					matrix[i][j] = 1 + matrix[i + 1][j + 1]
				else:
					matrix[i][j] = max(matrix[i + 1][j], matrix[i][j + 1])
		return matrix[0][0]


class Solution:

	def build_bridges(self, str1, str2):
		N = len(str1)
		M = len(str2)
		dp = [[0 for j in str2] for i in str1]
		for i in range(N):
			for j in range(M):
				a = (dp[i - 1][j - 1] if i > 0 and j > 0 else 0) + (1 if str2[j] == str1[i] else 0)
				b = dp[i - 1][j] if i > 0 else 0
				c = dp[i][j - 1] if j > 0 else 0
				dp[i][j] = max(a, b, c)
		return dp[N - 1][M - 1]


class Solution:

	def build_bridges(self, str1, str2):
		(m, n) = (len(str1), len(str2))
		(prev, cur) = ([0] * (n + 1), [0] * (n + 1))
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if str1[i - 1] == str2[j - 1]:
					cur[j] = 1 + prev[j - 1]
				elif cur[j - 1] > prev[j]:
					cur[j] = cur[j - 1]
				else:
					cur[j] = prev[j]
			(cur, prev) = (prev, cur)
		return prev[n]


class Solution:

	def build_bridges(self, a, b):
		m = len(a)
		n = len(b)
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if b[i - 1] == a[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[n][m]


class Solution:

	def build_bridges(self, s1, s2):
		m = len(s1)
		n = len(s2)
		t = []
		for i in range(m + 1):
			a = []
			for j in range(n + 1):
				a.append(0)
			t.append(a)
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
				elif s1[i - 1] == s2[j - 1]:
					t[i][j] = t[i - 1][j - 1] + 1
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return t[m][n]


class Solution:

	def build_bridges(self, str1, str2):
		d = dict()

		def lcs(str1, str2, n, m):
			if n == 0 or m == 0:
				return 0
			if (n, m) in d:
				return d[n, m]
			if str1[n - 1] == str2[m - 1]:
				return 1 + lcs(str1, str2, n - 1, m - 1)
			d[n, m] = max(lcs(str1, str2, n, m - 1), lcs(str1, str2, n - 1, m))
			return d[n, m]
		return lcs(str1, str2, len(str1), len(str2))


class Solution:

	def build_bridges(self, str1, str2):
		n1 = len(str1)
		n2 = len(str2)
		dp = []
		for i in range(n1 + 1):
			l = []
			for j in range(n2 + 1):
				l.append(0)
			dp.append(l)
		for i in range(n1 + 1):
			for j in range(n2 + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif str1[i - 1] == str2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[n1][n2]


class Solution:

	def lcs(self, X, Y, m, n):
		t = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
				elif X[i - 1] == Y[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return t[m][n]

	def build_bridges(self, str1, str2):
		m = len(str1)
		n = len(str2)
		return self.lcs(str1, str2, m, n)


import numpy as np

class Solution:

	def build_bridges(self, str1, str2):
		m = len(str1)
		n = len(str2)
		matrix = np.zeros([m + 1, n + 1], dtype=int)
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if str1[i - 1] == str2[j - 1]:
					matrix[i][j] = matrix[i - 1][j - 1] + 1
				else:
					matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1])
		return matrix[m][n]


class Solution:

	def solve(self, memo, i, j, s1, s2):
		if i == len(s1) or j == len(s2):
			return 0
		if memo[i][j] > 0:
			return memo[i][j]
		if s1[i] == s2[j]:
			memo[i][j] = 1 + self.solve(memo, i + 1, j + 1, s1, s2)
			return memo[i][j]
		else:
			memo[i][j] = max(self.solve(memo, i + 1, j, s1, s2), self.solve(memo, i, j + 1, s1, s2))
			return memo[i][j]

	def build_bridges(self, str1, str2):
		memo = [[-1 for i in range(0, len(str2))] for j in range(0, len(str1))]
		return self.solve(memo, 0, 0, str1, str2)


class Solution:

	def build_bridges(self, str1, str2):
		if str1 == str2:
			return len(str1)
		n = len(str1)
		m = len(str2)
		d = [[0 for c in range(m + 1)] for r in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if str1[i - 1] == str2[j - 1]:
					d[i][j] = d[i - 1][j - 1] + 1
				else:
					d[i][j] = max(d[i - 1][j], d[i][j - 1])
		return d[n][m]


class Solution:

	def build_bridges(self, str1, str2):
		lcs = [[0] * (len(str1) + 1) for _ in range(len(str2) + 1)]
		for idx in range(len(str1) + 1):
			lcs[len(str2)][idx] = 0
		for idx in range(len(str2) + 1):
			lcs[idx][len(str1)] = 0
		for i in range(len(str2) - 1, -1, -1):
			for j in range(len(str1) - 1, -1, -1):
				if str1[j] == str2[i]:
					lcs[i][j] = 1 + lcs[i + 1][j + 1]
				else:
					lcs[i][j] = max(lcs[i][j + 1], lcs[i + 1][j])
		return lcs[0][0]


class Solution:

	def build_bridges(self, str1, str2):
		dp = []
		for i in range(len(str2) + 1):
			dp.append([0] * (len(str1) + 1))
			for j in range(len(str1) + 1):
				if i > 0 and j > 0:
					if str2[i - 1] == str1[j - 1]:
						dp[i][j] = dp[i - 1][j - 1] + 1
					else:
						dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[-1][-1]