44. DP on strings

 1. LCS-⭐

we will find answer through the way of generating all subsequences
------------
1. Express everything in terms of indices
2. Explore all possibilities on that indices
3. take the best among them
----------




------------------
a) Recursion Approach-

1. if char at i & j matches => do 1+f(i-1,j-1)
2. if char at i & j do not matches => do f(i-1,j) + f(i,j-1)   => explore both possibilities by moving 1 ptr at a time
----------------
b) Memoization✅

--------------------
c) Tabulation- 

since we can't write base case of recursion into tabulation with negative indices so we do a shifting of indices to right by 1 which means now f(i,j) will mean we want LCS of str1 till i-1 with str2 till j-1

we can also space optimize this solution using curr & prev vectors

--------------------------------------------------------------------------------------------------------------------------

2. Print LCS

we will backtrack over dp table

below is table we got from LCS length count's tabulation/ bottom to up soln-
for,
str1: abcde     ,str2: bdqek

here dp[i][j] is a state telling what is longest length for both strings upto i and j index
JAHA JAHA EK NUMBER PEHLI PEHLI BAAR AARA , WAHA(i,j) SAME CHAR HAI

below is the soln after building dp table-

---------------------------------------------------------------------------------------------------------------------------
3. Longest Common Substring-
simple variation of LCS(subseq)

unlike subsequence here in the dp table, an element do not depend for its count on neighbors, however we do take into account count of diagonally above element if curr element at s1[i] matches with s2[j] 
so we get contiguous substring of max length

1. at i, j check if s1[i] matches with s2[j] 
2. if no, value is 0
3. if yes, value is 1 & if diagonally above element is non-zero (say x) then curr value is x+1
--------------------------------------------------------

-----------------------------------------------------------------------------------------------------------------------------
4. Longest Palindromic Subsequence-
(in a given string)
Simple variation of LCS with both strings same & i start from n-1 & j from 0 so a minor change in base case too...
----------------------------------------------------------------------------------------------------------------------------
5. Min insertions to make entire string palindromic-

Simple variation of longest palindromic subsequence (LPS)

ans = n- length of LPS

---------------------------------------------------------------------------------------------------------------------------
6. Min delete ops to make 2 strings same-
or, min insert/del ops to convert string A to B

simple variation of LCS-
e.g., if str1 has length 5 and str2 has length 3 and LCS has length 2 then delete ops are: 
(5-2)+(3-2)   or  (n+m)-(2*LCS)
-------------------------------------------------------------------------------------------------------------------------

                    7. Shortest common SUPER-SEQUENCE-⭐

simple variation of LCS-
---------------------
Approach-1:

LCS ke har char se pehle waale chars dono strings se uthake ans mein insert krte jaao
e.g., ans is (bg r uoo t e) for (brute , groot)

----------------------------------------------------------
Approach-2 :
printing LCS ka variation, bas yaha jab s1[i] != s2[j] ho, tb bhi hum ans mein add krenge
we get etorbg so, reversing it gives us the answer
-----------------------------------------------------------------------------------------------------------------------------
                                    8. Distinct Subsequences-

Find no. of distinct subsequences in a string s , which are equal to string t.

agar same characters hain dono mein i aur j pe toh ya toh lelo ya aage fir kbhi lelena
agar same ni hai toh s string mein aage badho, not pick wala case hai ye

We can optimise it to- tabulation, 2 arrays space optimisation, even we can use just 1 array optimization
-----------------------------------------------------------------------------------------------------------------------------
                                           9. Edit distance-⭐
convert string 1 to string 2 with 3 operations- insert, delete, replace
find min ops needed to do so

e.g., (intention , execution) goes as below-
i--->e :                       e        (op+1)    REPLACE
n--->x :                      ex      (op+1)    REPLACE
t---> delete :              ex      (op+1)    DELETE
e--->matches:            exe    (op+0)    MATCH
n->c:                         exec   (op+1)    REPLACE
insert u:                    execu (op+1)     INSERT

-----------------------------------------------------------------------------------------------------------------------------
10. Wildcard Matching-🔥🔥

we will try all possible ways for a * to match an unknown length sequence

BASE CASES-
1. pattern string exhausted- if(other string also exhausted) return true, else false;
2 og string exhausted- if(all left chars in pattern string are *) then return true
---------------------------------------------------------
Tabulation-

-------------------------------------------------------------------------------------------------------------

Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more