Sentence Similarity III | 2 Simple Approaches | Dry Run | Leetcode 1813 | codestorywithMIK
452Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
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) - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/strings/Sentence Similarity III.cpp
Leetcode Link : https://leetcode.com/problems/sentence-similarity-iii
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/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