Decode String - Leetcode 394 - Python
Vložit
- čas přidán 23. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
Problem Link: leetcode.com/problems/decode-...
0:00 - Read the problem
3:45 - Drawing Explanation
12:07 - Coding Explanation
leetcode 394
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#decode #string #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Very comprehensive problem to practice stacks! Together with asteroid collision and daily temps, one can argue understanding those 3 problems alone are a solid prep for stack problems on interviews.
this was asked in my amazon sde 1 interview somehow i managed t solved it. holy cow!
Wow, they ask such difficult questions for sde 1? Congrats on solving it!
You have my respect
Did this myself and came to see the solution. I am so happy to see my progress. Thank you soooo much!!!
I know you probably hear this a lot but your explanations are so clear and easy to grasp. Thanks a ton for this.
It's no wonder Google hired him in a heartbeat.
NeetCode has a great talent for reducing complex problems into simplest and digestible way.
Amazingly explained, was able to implement without even looking at code. Thank you!
Great explanation and diagrams!! This is what I got:
The things to decode have this pattern: Coefficient(content)
2 things needed:coefficient, and content
My approach using stack was adding just the {}, and tracking the indexes for substring
, but I like your approach is cleaner by adding everything to stack.
General approach:
for all chars in string
if stack is Empty:
if isDigit: calculate the numerical part/coefficient,
if (, add to stack, save startindex
if is character, add to string builder
if stack is not empty:
add everything
if is ), remove from stack
if stack is empty, recursively call helper(s.substring(startIndex+1, endIndex)
You explain these problems so well! can you please do a video on the problem " Guess the word" ?
One of the best solution availabe on YT. Great work sir. Huge fan of the way you break tough and/or complex problems into simpler versions!!😍😍
Love your videos, the clearest explainations I've come across among all the other ones ... Keep it up!
You make things feel so easy!
Thank you so much 😀
Then maybe its just me who still didn't understood it.
@@varunshrivastava2706 I would ask that you watch it again if so and jott what you can as you follow along
Bless🙏
First coding channel on CZcams that I put the bell icon to receive all updates for !!
Same
Best explanation as always!
wow usually I feel a bit anxious when not able to come up with a soln, I have been watching ur few vids! explanations r crisp and easy to understand, I even like it's in python while I code in cpp lol
Best explanation man! TYSM for your efforts.
Explanation put very simple way, thanks for this!
This is actually the best tutorial I found on the internet
Great clear explanation as always. thanks
Terrific explanation!!
I don't know why I am still using java. I came up with the same solution with a stack but it is at least twice longer thanks to java. This is so easy to read and comprehend.
Lol same bro. Python is the best language for interviews in my opinion.
Thanks, i ended up solving this with recursion on my first attempt. I used this video to learn how to apply stacks to the problem. Thank you.
This is the way better solution than official ones
Great video! Thanks! This problem showed me stacks are amazing for accruing and backtracking in an organic way!
You are coding god, man. You're in my idol list, right next Van Halen!
WOW. the solution and explanation is simply superb!!
According to LeetCode premium, the time complexity of this solution is actually O(maxK^countK * n), where maxK is the maximum value of k, countK is the count of nested k values and n is the maximum length of the encoded string. Example, for s = 20[a10[bc]], maxK is 20, countK is 2 as there are 2 nested k values (20 and 10). Also, there are 2 encoded strings a and bc with the maximum length of the encoded string n as 2.
A very excellent problem and explanation!
this is a very good explanation, very concise and clear code. I implemented this in C++ and got 100% time and 96% memory.
please send me cpp code i am getting wrong answer in one test case
This is my code:
class Solution
{
public:
string stuff(int n,string s)
{
string t;
while(n--) t+=s;
return t;
}
int stringToNum(string s)
{
int num=0;
for(int i=0;i
Man this is so easy in python .. i was doing it in C++ . i had the same logic but implementation was so tough for it
much easier to understand than upvoted solutions which I could never do interview.
Well explained.
Your way of explanation awsome
i think if we consider the length of the output string is K
then the time complx will be linear in this length K -> O(k) ;
You are amazing, Thanks a lot
Lots of love
Thanks for the video. Can you also do the Encode verion of this the (Leetcode 471) ?
great video, thanks
thank you so much sir for this amazing explaination🙇♂❤
Thanks bro u the man
very neat code
Great explanation !!
I was wondering whether we can do it solely by recursion calls?
yes you can
Just got this for a new grad position and I failed it miserably, should have watched more vids :(
Is there a reason you always do range(len(s)) instead of for x in s or enumerate(s)? I've been watching a lot of of these (great) videos and I noticed that, so I'm wondering...
thank you sir
How long do you actually take to solve these questions for the first time? It seems to take more than 1.5hrs for me.
I solved this a different way in linear time by using two stacks; one of factors where the top of the stack is the last number for the characters and another stack containing the substrings. whenever a ] character is detected it pops the two from their respective stacks, multiplies them, then appends it to the next top of the characters stack.
can you share your solution i am thinking in the same way
U a God
I was giving this problem for google's phone interview today. I didn't do as well :(
recursive is same as maintaining our own stack
GOAT
Amazing explanation but i cant think of why i cant solve it by myself
what is the space complexity?
stack makes this problem pretty much easier
Very Nice Explanation. Thanks, Buddy...
I did everything same except :
substr+=stack.pop()
and finally, substr=substr[::-1]
and similar for k
how m i am failing a test case. Could you please explain the difference ?
Failed test case:"3[z]2[2[y]pq4[2[jk]e1[f]]]ef"
I guess you essentially have substr = substr + pop instead of pop + substr, so the order of letters are not the same.
I even getting the wrong answer in cpp with the same test you failed.Please tell where i did wrong.
class Solution
{
public:
string stuff(int n,string s)
{
string t;
while(n--) t+=s;
return t;
}
int stringToNum(string s)
{
int num=0;
for(int i=0;i
This was asked in Zoho software developer role
It's much easier to write it in Python than in Java.
And even easier in Kotlin 😉
🐐
should line 16: k = stack.pop() * 10 +k ?
Then the digits of K number would be in the wrong order.
Popping from the stack retrieves the digits in reverse order.
Stepping it through in a debugger makes it easy to see.
can any one explain the time complexity of it
support
Thank you so much sir for your great and clear explanation.
Here the code in c++ :-
class Solution {
public:
string decodeString(string s) {
string ans="", substr="", k;
int n=s.size();
stack st;
for(int i=0; i
can anyone help me in solving it in recursively
is there another way to solve this without using Stack?
Can someone compare iterative solution vs recursive solution, in terms of time complexity and suggest which one is better approach?
Same thing.
No difference
The example showed with 54[ab] which has a 2 digits number. But the solution doesn't account for it. Hope you have time to update the video.
Actually it does.
Line 15 while loop builds a string which then gets converted to Int on Line 17.
@@CostaKazistov Thank you! It's my bad, sorry.
It seems leetcode added a testcase and this code no longer works
**This Works**
class Solution:
def decodeString(self, s: str) -> str:
out_str = []
digit = 0
for i in range(len(s)):
if s[i] != "]":
out_str.append(s[i])
if s[i].isdigit():
digit += 1
else:
sub_str = ""
while out_str[-1] != "[":
sub_str = out_str.pop() + sub_str
out_str.pop()
n = ""
while out_str and out_str[-1].isdigit():
n = out_str.pop() + n
n = int(n)
out_str.append(int(n)*sub_str)
if digit == len(s):
return ""
else:
return "".join(out_str)
It is so difficult to put Sting and Character in the same stack.
in java
I don't think the code can cover the corner case as "3"
Need recursive solution
Recursive solution would be easier to code up, yes.
But the above solution would be preferred in an interview setting.
C# code for above logic :
public static class AppHelper
{
public static String DecodeString(String s)
{
Stack st = new Stack();
for (int i = 0; i < s.Length; i++)
{
if (s[i] != ']')
{
st.Push(s[i]);
}
else
{
string curr_str = "";
while (st.Peek() != '[')
{
curr_str = st.Peek() + curr_str;
st.Pop();
}
st.Pop();
string number = "";
while (st.Count > 0 && Char.IsDigit(st.Peek()))
{
number = st.Peek() + number;
st.Pop();
}
int noKTimes = Convert.ToInt32(number);
while (noKTimes > 0)
{
for (int p = 0; p < curr_str.Length; p++)
{
st.Push(curr_str[p]);
}
noKTimes--;
}
}
}
s = "";
while (st.Count > 0)
{
s = st.Peek() + s;
st.Pop();
}
return s;
}
}
my c++ solution(same logic as explained in the video):
class Solution {
public:
string decodeString(string s) {
stack stk;
string str = "";
for(auto it: s) {
if(it >= 'a' and it = '0' and it = "0" and stk.top() 0) counts = stoi(count);
for(int i = 0; i < counts - 1; i++) str += str1;
stk.push(str);
}
}
string ans = "";
while(!stk.empty()) {
ans = stk.top() + ans.substr(0, ans.length());
stk.pop();
}
return ans;
}
};
the part where you did “while stack and stack[-1].isdigit():” kinda confuses me. Isn’t the stack always nonempty? There always has to be an integer in front of ‘[‘, otherwise we don’t even need to use brackets. Validating whether the stack is empty or not doesn’t seem to be necessary, but the code doesn’t work if I don’t validate it. I’m so lost here
If our input is "23[a]", when we get to line 15 our stack will contain just [2, 3], we have to keep popping numbers but we need to stop once the stack is empty else we'll get an index error when doing stack[-1].isdigit() check.
The isdigit() check catches the following case: input = 23[a4[b]] then our stack will be [2, 3, [, a, 4] when we get to that line 15, isdigit() will make sure we don't pop past the number 4 for the current substring we're building.
@@D_T244 ohh i didnt consider the case where the integer is a 2digit number. Thansk!!
wow
can you do this using recurssion
i don't understand why does it work
Instead of concatenating to string, I appended them all to a list, and called list.reverse() 😅😅
p.s. Stop scrolling comments, and solve some probolems.
every time he said "IN PYTHON", I was looking at my Java code, it was like speaking to me: What? don't look at me like that, go and search on google.
GOAT