LeetCode Decode String Solution Explained - Java
Vložit
- čas přidán 7. 09. 2019
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow My Twitter - / nicholaswwhite
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering - Věda a technologie
This question pissed me off to the depths of hell
Same here
I feel you bro. This question fucked up my brain
same I had it on a microsoft interview,
the main purpose of the question is to annoy the coder.
loll same
No one.
literally no one.
Nick White : "Uhh, Its pretty straight forward."
@@parmoksha correct!
It is always suggested to NOT use Java's 'Stack' implementation during coding interviews and instead 'Deque' could be used. This is because java's Stack implementation extends Vector which is a synchronised data structure and hence must not be preferred for data which do not require synchronisation. Also, Deque is an interface implemented by LinkedList which holds it as an advantage over Stack, which is a class.
Why would I think of using two stacks in the first place! :/
So that the latest added decoded string be stored and fetched. LIFO. Every string formed between [ and [ also need to handled.
My coding practice routine usually involves being unable to solve medium level questions on leetcode and then coming to your channel for guidance. Your explanation, although a bit fast for my sorry brain, was very helpful.
Do u create these explanation videos once you've practiced the questions yourselves or is it just fresh off the list??
That brain freeze was so relatable. I go completely blank on many questions. Any tips??
@@manansurana2606 You got that exactly right. I still have a long way to go, but since I wrote my previous comment, I've reached a stage where I may be able to recall a similar problem I might've seen previously and apply that to the problem at hand. This means not blanking out on ALL questions.
I think spaced repetition is key so my bedtime routine now involves chanting Dijkstra's, Bellman-Ford, Floyd-Warshall, Tarjan's, etc.
Man, 100 problems seems like a great speed if you're starting out on Leetcode, considering if your day job keeps you occupied. Good luck to you. Happy to connect on LinkedIn. Sent you a connection request.
Hey what does the StringBuilder temp= new sB(result.pop()) do ?
Your solution and coding of it was nice, so thank you!
Suggestion:
-I think it would have been helpful if you ran through the solution with an example because the thought/intuition behind the solution could have been explained further for better understanding.
nice and neat solution. Thanks for the upload!
Dont you get null pointer at line 21 when lets say string is [abc]2[a] ?
Hell is a place where you're told to solve everything recursively and the call never stack exceeds.
it's always good if you could come up with tracing the algo and parallelly code.. so that it is easy to understand.. anyways good effort
Hey Nick, thanks for the explanation. I came across this question today in an interview. I did not come up with 2 stacks approach. It's very hard to come up with this approach if you haven't already solved on leetcode.
which company ? Could you please share with us ?
Great video. Just 1 suggestion, Could you dry run it and explain just any 1 example so beginers can understand it better.
Pls elaborate the explainnation taking some test case then write the code all are not pro in leetcode
If there's a substring before a number, like "ab2[cd]", when does "ab" ever get added to res?
that's what we keep track of in the else part and add it along when we hit ']'
Excellent Nick. Where can I find the source code for this?
Nice logic Nick
You are a genious. I would see that a companies would not hire you because you can discover many problems that they choose not to look at. I am hoping one day you make something brilliant out of your mind. The way you explain something is so effortless. I am jealous and amaze to see your talent.
Can someone compare iterative solution vs recursive solution, in terms of time complexity and suggest which one is better approach?
Both iterative and recursive solutions are with O(n) complxity.
Thank you, well understood.
You have result stack and just push once and don’t do anything with it? This code will break in certain use cases.
Very well explained. Thank you for the detailed explanation.
Thank you for this video, Nick! Really appreciate what you do!
whats the time complexity for this solution?
O(n)
@@alokesh985 Why O(n)?
Hey, that's a good explanation, however instead of initializing the StringBuilder, you can just declare it before the iterative while loop and reset it every-time you encounter a new closing bracket and then start a fresh append from the pop. Something like this
StringBuilder segmentBuilder = new StringBuilder();
int segmentRepeatCount =0;
while(.....){
else if (encodedString.charAt(i) == ']') {
segmentBuilder.setLength(0);
segmentBuilder.append(words.pop());
segmentRepeatCount = counts.pop();
for (int k = 0; k < segmentRepeatCount; k++) {
segmentBuilder.append(result);
}
result = segmentBuilder.toString();
i++;
}....}
This will optimize the solution further.
What was the intuition behind using a stack in this question?
if you see parenthesis question anywhere always think of stack solution first.
The intuition is that when you are required to store some elements/substring/values for a later use, jump into the next set of values, process them and then come back to the values stored earlier and process them at a later point of time, that's when you go for a Stack, because that's exactly what a stack does. Here, since we need to store 2 different kinds of values (numbers and the strings), we are forced to choose 2 separate stacks.
Also, just as an additional information, it is always suggested to NOT use Java's 'Stack' implementation during coding interviews and instead 'Deque' could be used. This is because java's Stack implementation extends Vector which is a synchronised data structure and hence must not be preferred for data which do not require synchronisation. Also, Deque is an interface implemented by LinkedList which holds it as an advantage over Stack, which is a class.
Runtime & Space complexity?
Space would be O( length of string ) as we are creating 2 stacks whose lengths add upto the length of string. Since we are not adding the brackets in the stack so is big O not theta . Time would be length of string multiplied by the no of time the particular string is repeated ... , we are just doing a loop over the string characters and then a inner loop for numeric value i.e number of times the string is repeated ...so we can say its O(N* M) ,where m is the sum total of number of times we want our substrings to be repeated , comparisons are of constant time as well as the push and pop operations .
The logic is kinda very hard to think. How could you come up with this solution??
i feel you bro. my brain was fucked.
@@hacker-7214 There are lots of discussions on leetcode. Just spend some time on reading through.
Yep, this kind of solution is too elegant and too neat to come with in one go.
He didn't. He solved it 10 times before that.
why minus zero on line 12?
That's because you want to trace the number exactly. Ascii value of 0 is 48 and 9 is 57. So you actually do 57-48 so as to get 9
@@tirthdoshi7463 why not simply 57 then ?
@@stonecoldcold2941 Bcus everything starts with 0 and in this case 0 is 48. Base is 48 and that's why when you iterate through char array, always minus to base value. Say if it's a which is 65. d - a is 68 - 65 : 4 a -> d is 4
No offence, but if you are seriously asking this question. Then this problem is too difficult for your level.
@@MrNetsecure No offence but that's why she is here to understand the solution. I hope everyone has something difficult to deal with. Cheers!
You forgot adding the # of this leetcode question
you are awesome man
instead of using res variable, it is better to use a StringBuilder as string concatenation is a costly operation
U could have explained it with an example before starting implementation
Thank you
I'd rather suggest a recursion solution that is much more intuitive and weirdly ran in 0ms.
string getString(string s,int n,int &i)
{
string res;
int ct=0;
string val;
while(i=97 && s[i]='0' && s[i]
Super
IR :(
Currently it's 9ms in Leetcode..... : ()
It would be nice if you explained the solution more seriously instead of emphasizing how blanked out you were. You're supposed to teach people who are seeing this for the first time, not those who are reviewing it again and already write the code by heart (like you did).
excellent
Sorry but u didn't explain it well
He seems high
not optimal solution, you gotta use recursion