@@ -20,4 +20,79 @@ class Solution {
2020}
2121return dp[M ][N ]
2222}
23- }
23+ }
24+
25+ /*
26+ * Different solutions
27+ */
28+
29+ // Recursion + Memoization, Time Complexity of O(n * m) and space complexity of O(n * m)
30+ class Solution {
31+ fun longestCommonSubsequence (t1 : String ,t2 : String ):Int {
32+ val n= t1.length
33+ val m= t2.length
34+ val dp= Array (n) {IntArray (m) {- 1 } }
35+
36+ fun dfs (i : Int ,j : Int ):Int {
37+ if (i== n|| j== m)return 0
38+ if (dp[i][j]!= - 1 )return dp[i][j]
39+
40+ if (t1[i]== t2[j])
41+ dp[i][j]= 1 + dfs(i+ 1 , j+ 1 )
42+ else
43+ dp[i][j]= maxOf(dfs(i+ 1 , j), dfs(i, j+ 1 ))
44+
45+ return dp[i][j]
46+ }
47+
48+ return dfs(0 ,0 )
49+ }
50+ }
51+
52+ // Top down DP, Time Complexity of O(n * m) and space complexity of O(n * m)
53+ class Solution {
54+ fun longestCommonSubsequence (t1 : String ,t2 : String ):Int {
55+ val n= t1.length
56+ val m= t2.length
57+ val dp= Array (n+ 1 ) {IntArray (m+ 1 ) }
58+
59+ for (iin n- 1 downTo0 ) {
60+ for (jin m- 1 downTo0 ) {
61+ if (t1[i]== t2[j])
62+ dp[i][j]= 1 + dp[i+ 1 ][j+ 1 ]
63+ else
64+ dp[i][j]= maxOf(dp[i+ 1 ][j], dp[i][j+ 1 ])
65+ }
66+ }
67+
68+ return dp[0 ][0 ]
69+ }
70+ }
71+
72+ // Optimized DP (Works both for both Top-down and Bottom-up, but here we use bottom-up approach)
73+ // Time Complexity of O(n * m) and space complexity of O(maxOf(n, m))
74+ class Solution {
75+ fun longestCommonSubsequence (t1 : String ,t2 : String ):Int {
76+ val m= t1.length
77+ val n= t2.length
78+ if (m< n)return longestCommonSubsequence(t2, t1)
79+
80+ var dp= IntArray (n+ 1 )
81+
82+ for (iin m downTo0 ) {
83+ var newDp= IntArray (n+ 1 )
84+ for (jin n downTo0 ) {
85+ if (i== m|| j== n) {
86+ newDp[j]= 0
87+ }else if (t1[i]== t2[j]) {
88+ newDp[j]= 1 + dp[j+ 1 ]
89+ }else {
90+ newDp[j]= maxOf(dp[j], newDp[j+ 1 ])
91+ }
92+ }
93+ dp= newDp
94+ }
95+
96+ return dp[0 ]
97+ }
98+ }