Regular Expression Matching: 10 - Dynamic Programming interview - google,apple,amazon,meta,microsoft

#dynamicprogramming #string #recursion #leetcode #hard #technical #interview #question #problem #softwareengineer #developer #optimalsolution #bruteforce #googleinterview #amazoninterview #facebookinterview #appleinterview #microsoftinterview #google #facebook #microsoft #amazon #apple #meta #bloomberg #timecomplexity #spacecomplexity #infosys #tcs

Learn to solve this amazing Leetcode hard, Dynamic Programming + string + recursion problem that has been asked in hundreds of technical interviews at companies like Google, Facebook, linked in, Microsoft, Meta, apple, Uber.

LeetCode Problem: Regular Expression Matching
Leetcode: 10

Not stopping till we get employed in FAANG.

This Problem was recently asked in following companies in Technical Coding Interview:

Microsoft technical interviews,
Amazon technical interviews,
Google technical interviews,
Facebook technical interviews,
Apple technical interviews,
Bloomberg technical interviews,
Nvidia technical interviews,
Adobe technical interviews,
Uber technical interviews,
JPMorgan technical interviews,
Snapchat technical interviews,
Yahoo technical interviews,
instacart technical interviews,
Coursera technical interviews,
eBay technical interviews,
Tesla technical interviews,
PayTM technical interviews,
Twitter technical interviews,
Airbnb technical interviews,

-------------------------------------------------------------------------------------------------------------------------
(Contact me for Business Inquiries):

GitHub Repository for Questions solved so far:

(Support the channel, if videos helps you in any manner... Give me a Coffee)

About me and My Purpose:

I am a software engineer with 5+ years of experience @ Non-FAANG company. I have always been bad at coding and really bad at programming interviews. So, once I got employed in IT industry, I only worked on operational activities (just so I can avoid coding).

But deep down I always wanted to work at an Elite IT company. So, I decided to face my fears, and to master coding & technical Interviews. I started with LeetCoding 1 problem a day. But I was facing issues with consistency, I would solve LC problems for week, and then drop it for 2-3 weeks. This lasted till 6 months.

And upon deeper investigation I found that I was not committed enough. Then suddenly my wife gave me an idea, that rather then focusing on solving a LC problem for my-self, why don't I commit to make videos on solving the LC problems. And try to complete at-least one video every alternate day. Hence, I started this channel.

My ultimate aim is to get into FAANG company, and also create a channel in such a way that anyone wants to get into FAANG, if they just follow my channel, they should be able to clear all the FAANG Technical Interviews.

Here are few more reasons on why I started the channel.

1) To have a motive for me to solve leetcode problems.
2) In order to solve a LC problem, first I have to really understand the problem and explain my thought process, which solidifies my concepts.
3) I can document my progress. Also learn a new skill on how to run a YT channel.
4) My work can help other software engineers.
5) I can have something cool to mention in my linked-in and resume.
-----------------------------------------------------------------------------------------------------------------------------------

Here is a list of my dream Companies:

FAANG,
Meta,
Facebook,
Google,
Amazon,
Netflix,
Microsoft,
apple,
doordash,
roblox,
stripe,
instacart,
uber,
lyft,
twitter,
linked In,
pinetrest,
bloomberg,
robinhood,
Goldman Sachs,
box,
two sigma,
byte dance,
tik tok,
air bnb,
nuro,
ui path,
oracle,
twitch,
data bricks,
waymo,
dropbox,
coinbase,
snowflake,
snap,
nvdia,
broadcom,
slack,
intel,
cisco,
indeed,
salesforce,
reddit,
wayfair,
okta,
splunk,
service now,
coursera,
square,
upgrade,
mozilla,
yelp,
unity,
ebay,
affirm,
stach adapt,
amplitude,
github,
wish,
brex,
etsy,
chime,
shopify,
amd,
GoDaddy,
IBM

Introduction: 00:00
Understanding the Problem Statement: 00:38
Considering All Possiblities: 05:06
Optimal Solution: 12:40
Coding: 24:22

[divyas]

toooo good explanation, tysm. a suggestion pls the make volume little bit high

[DestinationFAANG]

Java Solution


class Solution {
public boolean isMatch(String s, String p) {

if(s == null || p == null){
return false;
}

boolean[][] dp = new
dp[0][0] = true;

for(int i=0; i<p.length(); i++){
if(p.charAt(i) == '*' && dp[0][i-1]){
dp[0][i+1] = true;
}
}

for(int i=0; i<s.length(); i++){
for(int j=0; j<p.length(); j++){

if(p.charAt(j) =='.'){
dp[i+1][j+1] = dp[i][j];
}
if(p.charAt(j) == s.charAt(i)){
dp[i+1][j+1] = dp[i][j];
}

if(p.charAt(j) == '*'){

if(p.charAt(j-1)!= s.charAt(i) && p.charAt(j-1)!= '.'){
dp[i+1][j+1] = dp[i+1][j-1];
}

else{
dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
}

}

}
}

return dp[s.length()][p.length()];



}
}

[ruturajghodekar]

Hi I'm 21, currently pursuing FY MscCA, my first mistake was not getting into data structures and learning problem solving, saw the blind 75 sheet and started, solving problems, thts when I reached your channel, want to crack to good package in atleast the next 5-6 months, would you help me? Getting where I want to go,
It's like having having a mentor or a gym partner with whom you push yourself, its definitely fine otherwise, i do learn from the your DSA lects