Sentence Similarity III | 2 Simple Approaches | Dry Run | Leetcode 1813 | codestorywithMIK

Подписаться 69 тыс.

Просмотров 8 тыс.

50% 1

Whatsapp Community Link : www.whatsapp.c...
This is the 44th Video of our Playlist "Strings : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a good String based Problem : Sentence Similarity III | 2 Simple Approaches | Dry Run | Leetcode 1813 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Sentence Similarity III | 2 Simple Approaches | Dry Run | Leetcode 1813 | codestorywithMIK
Company Tags : will update soon
My solutions on Github(C++ & JAVA) - github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZ...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Using Vectors/Lists
Logic: The solution uses two lists (vec1 and vec2) to store the words from both input sentences (s1 and s2). The algorithm checks for similarity by matching words from the start (prefix) and the end (suffix) of both lists.
Steps:
Split s1 and s2 into lists of words.
Increment pointers from the beginning until the words mismatch.
Decrement pointers from the end until the words mismatch.
Check if all words of s2 are matched within s1.
Complexity: Efficient in time with a linear scan but uses extra space for storing two lists.
Key Operation: Checking for prefix and suffix matches using index pointers.
Approach 2: Using Deques
Logic: This approach uses two deques (deq1 and deq2) to store the words of the sentences. The algorithm removes matching words from both ends (front and back) until no more matches are found.
Steps:
Split s1 and s2 into deques.
Remove matching words from the front of both deques.
Remove matching words from the back of both deques.
If deq2 is empty at the end, s2 is a sub-sequence of s1.
Complexity: Similar to the first approach but uses deque operations (pollFirst, pollLast), which may have additional overhead.
Key Operation: Removing elements from the front and back until deq2 is exhausted.
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

Опубликовано:

9 окт 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 36

@gui-codes 4 дня назад

jab bhi free time mile please post Qn-3 of today's contest. Thanks a lot for this video bhaiya

@a_mans5895 4 дня назад

Bhaiyaa contest k solution bhi provide krdo bht problem aati unke solution likhne me or khi pe acche se solution milta bhi nhi most of the questions ka

@ashishj9497 4 дня назад

its a violation to publish answers to contest before contest ends

@Si_5454 4 дня назад

@@ashishj9497 Are bhai contest end hone k baad explanation chahiye pehle nhii

@peterfromengland8663 4 дня назад

I could only solve first 2 questions

@RohitKumar-dz8dh 4 дня назад

@@peterfromengland8663and I could only one 😢

@tonishant 4 дня назад

Checkout codingmohan for contest solution

@kapilvermani2575 4 дня назад

deque approach was really awesome!!

@bakulgarg8576 4 дня назад

One of the best DSA instructor on RU-vid ❤❤

@AshutoshAnand-o5l 4 дня назад

Goat for a reason!

@rockykumarverma980 4 дня назад

Thank you so much Bhaiya ji🙏🙏🙏

@fr4nkyyy720 4 дня назад

Thanks A lot bhaiiya , clearly understand the problem and solution, please keep pushing solution for us

@vivek_3107 4 дня назад

wah bhaii maza a gyaaaaa

@DipakKawale 3 дня назад

in case of deque implementation check this return len(q2)==0 or len(q1)==0

@jeehub041 4 дня назад

Bhaiya contest ka 3rd question please mast question ha graph ka🙏🙏🙏

@EB-ot8uu 4 дня назад

2nd approach was too good

@newglobal2056 4 дня назад

Bhaiya ajj contest ka 4'th waale solution provide karwa do pls

@wearevacationuncoverers 4 дня назад

thanks a lot mik

@souravjoshi2293 4 дня назад

thanks a lot

@ReshuSharma-jc7yu 4 дня назад

sir pls backtracking playlist pls

@cosmicthor7330 4 дня назад

bhaeeya aap ek while loop sey kr sktey they bs check krna tha deque2 empty hai ya nhi bcz upar aapney check kiya hai deque1 hamesha bara hai ,similarily vector1>vector2 toh while(p3

@vaibhav454 4 дня назад

Mohammad bhai make videos for all 4 ques of today LeetCode Contest

@RishabhChatterjee-fg2gz 4 дня назад

bhaiya bas prefix and suffix matching, ye observation nehi pakad paya isiliye video dekhne k baad solve karna pad raha hai

@nkd575 4 дня назад

pls provide the solution of last 2 ques of leetcode contest

@dhairyachauhan6622 3 дня назад

simple solution using recursion class Solution { public: vector buildSentence(string &s1){ string str; stringstream ss(s1); vectorarr; while(getline(ss,str,' ')){ arr.push_back(str); } return arr; } bool solve(vector&small,vector&large,int idx1,int idx2,bool canAdd){ if( (idx1 >= small.size() && idx2 >= large.size()) || (idx1>= small.size() && canAdd)){ return true; } if(idx1 >= small.size()){ return false; } if(idx2 >= large.size()){ return false; } if(small[idx1] == large[idx2]){ bool ahead = solve(small,large,idx1+1,idx2+1,canAdd); if(ahead){ return true; } } if(canAdd){ for(int i = idx2;i

@Arjun-Kumar-Pandey 4 дня назад

@codestorywithMIK 3311. Construct 2D Grid Matching Graph Layout make video on this question please

@soumyamakkar4677 4 дня назад

can someone explain me the solution of the second problem in today's contest

@jewelchakraborty9717 4 дня назад

My Thought Process - 1. The sus node is given which is k. 2. Now create a graph from the invocations array(this is basically the edges information). 3. Start from k and run a DFS on the graph you created in Step 2. 4. Mark all the nodes which you have visited in Step 3 using a vis[]. 5. Iterate over the invocations array. Suppose (u, v) is an element of the invocations array. If vis[u] == 0 && vis[v] == 1 that means u is not a sus node whereas v is a sus node and as (u, v) is an element of the array, u has an outgoing edge to v i.e. a non sus node has an edge to a sus node. Therefor, we will return all the nodes without removing anything. 6. Else just add those nodes in our result which are marked as non-visited in our vis array. /* MY JAVA CODE */ /* Passes all test cases */ class Solution { public void createGraph(List graph[], int[][] edges, int n){ for(int i = 0; i < n; i++){ graph[i] = new ArrayList(); } for(int i = 0; i < edges.length; i++){ int u = edges[i][0]; int v = edges[i][1]; graph[u].add(v); } } public void f(List graph[], int[] vis, int start){ vis[start] = 1; for(int i = 0; i < graph[start].size(); i++){ int adj = graph[start].get(i); if(vis[adj] == 0){ f(graph, vis, adj); } } } public List remainingMethods(int n, int k, int[][] edges) { List graph[] = new ArrayList[n]; createGraph(graph, edges, n); int[] vis = new int[n]; f(graph, vis, k); List res = new ArrayList(); int flag = 0; for(int i = 0; i < edges.length; i++){ int u = edges[i][0]; int v = edges[i][1]; if(vis[u] == 0 && vis[v] == 1){ flag = 1; break; } } if(flag == 1){ for(int i = 0; i < n; i++){ res.add(i); } return res; } for(int i = 0; i < n; i++){ if(vis[i] == 0){ res.add(i); } } return res; } }

@jeehub041 4 дня назад

My code in single while loop but same time complexity as sir🤣😇😁 bool areSentencesSimilar(string sentence1, string sentence2) { if(sentence1.size()< sentence2.size()) swap(sentence1,sentence2); stringstream ss1(sentence1); vector vec1, vec2; string temp; while(ss1>>temp) { vec1.push_back(temp); } stringstream ss2(sentence2); while(ss2>> temp) { vec2.push_back(temp); } int i=0, j=vec1.size()-1, l=0, m=vec2.size()-1; while(true) { if(l>m) return true; if(i=0 && vec1[j]==vec2[m]) { j--; m--; } else return false; } return true; }

@Si_5454 4 дня назад

Bhaiya contest ka ek bhi question nhi bna aaj kya karu.😢😢

@sidhanttiwari942 4 дня назад

Prepare for the next, like I do.Mere se toh 1 hee bnta h , i'm trying to reach towards solving that 2nd question

@vaibhavshahi5601 4 дня назад

Question 3 and 4 of contest😢

@gyandyan 4 дня назад

bool areSentencesSimilar(string s1, string s2) { if(s1.length()

@SHIVAMOJHA21 4 дня назад

MY DP BRUTE FORCE😂 class Solution: def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool: s1 = sentence1.split() s2 = sentence2.split() len1 = len(s1) len2 = len(s2) if len1 == len2: if s1 == s2: return 1 return 0 if len1 > len2: big = 1 else: big = 2 self.memo = {} return self.solve(0 , 0 , len1 , len2 , s1 , s2 , 0 , 1 , big) def solve(self , idx1 , idx2 , len1 , len2 , s1 , s2 , joined , seq , big): if (idx1 , idx2 , joined , seq) in self.memo: return self.memo[(idx1 , idx2 , joined , seq)] if idx1 >= len1 and idx2 >= len2: return 1 if idx1 >= len1: if big == 1: return 0 if joined == 0 or seq == 1: return 1 return 0 if idx2 >= len2: if big == 2: return 0 if joined == 0 or seq == 1: return 1 return 0 if s1[idx1] != s2[idx2]: if joined == 1 and seq == 0: return 0 if big == 1: self.memo[(idx1 , idx2 , joined , seq)] = self.solve(idx1+1 , idx2 , len1 , len2 , s1 , s2 , 1 , 1 , big) else: self.memo[(idx1 , idx2 , joined , seq)] = self.solve(idx1 , idx2+1 , len1 , len2 , s1 , s2 , 1 , 1 , big) else: if joined == 1: match = self.solve(idx1+1 , idx2+1 , len1 , len2 , s1 , s2 , joined , 0 , big) else: match = self.solve(idx1+1 , idx2+1 , len1 , len2 , s1 , s2 , joined , seq , big) not_match = 0 if big == 1: not_match = self.solve(idx1+1 , idx2 , len1 , len2 , s1 , s2 , 1 , 1 , big) else: not_match = self.solve(idx1 , idx2+1 , len1 , len2 , s1 , s2 , 1 , 1 , big) self.memo[(idx1 , idx2 , joined , seq)] = match or not_match return self.memo[(idx1 , idx2 , joined , seq)]