So the built-in function .split() come up in my mind, which is a good way to convert string into list, this will help a lot. Let's still take Neetcode's example of the path. If path is "/../abc//./def/", then path.split('/') gonna be [' ', '..', 'abc', ' ', '.', 'def', ' ']. And this is pretty easy to understand the if conditions in Neetcode's code. class Solution: def simplifyPath(self, path: str) -> str: stack = [] newPath = path.split('/') for c in newPath: if c == '..': if stack: stack.pop() elif c != '' and c != '.': stack.append(c) return '/' + '/'.join(stack)
appending a slash at the end of path and appending a slash when it returns makes code much easier to implement. I added many conditions and it is not easy to read. I learned a lot today too. Thank you so much!
Leetcode's solution is also good to understand was well: class Solution: def simplifyPath(self, path: str) -> str: # Initialize a stack stack = [] # Split the input string on "/" as the delimiter # and process each portion one by one for portion in path.split("/"): # If the current component is a "..", then # we pop an entry from the stack if it's non-empty if portion == "..": if stack: stack.pop() elif portion == "." or not portion: # A no-op for a "." or an empty string continue else: # Finally, a legitimate directory name, so we add it # to our stack stack.append(portion) # Stich together all the directory names together final_str = "/" + "/".join(stack) return final_str
Same but by just using split on path, makes it's easier to understand `path_arr = path.split("/") stack = [] for sec in path_arr: # section is not empty and section is not "." which means just current directory if sec != '' and sec != "." if sec == "..": # pop previous val in stack is sec is ".." if stack: stack.pop() else: stack.append(sec) res = "/" + "/".join(stack) return res`
I tried something like this without having to create cur variable. There are 2 conditions - one for double dot in which case we pop from the stack if stack is not empty. The second case is for single dot - we append into our stack if dir is not equal to single dot. class Solution: def simplifyPath(self, path: str) -> str: stack = [] path = path.replace('//','/') for dir in path.split('/'): if dir: if dir == '..': if stack: stack.pop() else: if dir != '.': stack.append(dir) return '/' + '/'.join(stack) Submission stats: Runtime: 35 ms, faster than 84.95% of Python3 online submissions for Simplify Path. Memory Usage: 13.9 MB, less than 37.47% of Python3 online submissions for Simplify Path.
class Solution: def simplifyPath(self, path: str) -> str: stack = [] path = path.split("/") for p in path: if stack and p == "..": stack.pop() if p.isalnum() or (p != "." and p != ".." and len(p) > 0): stack.append(p) return "/" + "/".join(stack)
I submitted the solution provided and it was a wrong answer for the test case: "/a//b////c/d//././/..". Therefore, I have modified the solution using while inside while loop and it was accepted. class Solution: def simplifyPath(self, path: str) -> str: stack = []
i = 0 while i < len(path): if path[i] == '/': i += 1 continue else: cur = '' while i < len(path) and path[i] != '/': cur += path[i] i += 1 if cur == '..': if stack: stack.pop() elif cur == '.' or cur == '': i += 1 continue else: stack.append(cur) return '/' + '/'.join(stack)
"join" traverses stack in the FIFO order, but stack is a LIFO order, so I think this property should not be called "stack" or the join method should not be used with stack.
I wonder how you approach while solving the question for the first time, how do you split it into smaller part or do you immediately come with the solution at once
A better simple way of the solving the question 1. replace all multiple occurring slashes to single slash 2. split the string by "/" 3. now perform the stack operations on the split string array class Solution: def simplifyPath(self, path: str) -> str: stack = [] while "//" in path: path = path.replace("//","/") splitted_string = path.split("/") #split the string with "/" and perform opertations over the stack for op in splitted_string: if op=="..": if stack: stack.pop() else: continue elif op=="." or op=="": continue else: stack.append(op) return "/"+"/".join(stack)
For this specific test case: path("/a//b////c/d//././/..") < -- realize there is a ".." at the end of this path, which means we need to pop from the top of their stack If we didn't include the "/" in our for loop, we'll get the wrong answer. I don't like this problem since it's very tricky. But oh well. We needed the "/" at the end of our for loop [for c in path + "/"] in order to pop the 'd'. Thus our answer would be '/a/b/c', not 'a/b/c/d' (if you removed the '/' in the for loop) Best way to explain it is to debug it, then you'll understand.
@@willowsongbird A simple example is take this case "/abc/def". If you don't add "/" to the end, you wouldn't add "def" to the stack, so ur ans would be "/abc", but if we add "/" to the input, our output will be "/abc/def" which is correct.
You have to use another stack , fill the new stack by popping elements of current stack . And pop each element from the new stack and make a string ans , ans += "/" + newstack->top() ;
I tried to do the join at the end in c# but it gave me the list in the wrong order, any idea why? public class Solution { public string SimplifyPath(string path) { Stack directories = new(); StringBuilder current = new(); // /home//foo// foreach(char character in (path + "/")){ if(character == '/'){ if(current.ToString() == ".."){ if(directories.Count > 0){ directories.Pop(); }
It's really nice that you started by explaining how the directory works. Very clear and organize video!
So the built-in function .split() come up in my mind, which is a good way to convert string into list, this will help a lot.
Let's still take Neetcode's example of the path. If path is "/../abc//./def/", then path.split('/') gonna be [' ', '..', 'abc', ' ', '.', 'def', ' ']. And this is pretty easy to understand the if conditions in Neetcode's code.
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
newPath = path.split('/')
for c in newPath:
if c == '..':
if stack:
stack.pop()
elif c != '' and c != '.':
stack.append(c)
return '/' + '/'.join(stack)
This is a simpler solution
This made the solution make alot more sense, thank you!
just had this question for google
appending a slash at the end of path and appending a slash when it returns makes code much easier to implement. I added many conditions and it is not easy to read. I learned a lot today too. Thank you so much!
Leetcode's solution is also good to understand was well:
class Solution:
def simplifyPath(self, path: str) -> str:
# Initialize a stack
stack = []
# Split the input string on "/" as the delimiter
# and process each portion one by one
for portion in path.split("/"):
# If the current component is a "..", then
# we pop an entry from the stack if it's non-empty
if portion == "..":
if stack:
stack.pop()
elif portion == "." or not portion:
# A no-op for a "." or an empty string
continue
else:
# Finally, a legitimate directory name, so we add it
# to our stack
stack.append(portion)
# Stich together all the directory names together
final_str = "/" + "/".join(stack)
return final_str
Personally I find leetcode solution more easy to understand
Honestly this is much more straightforward, thanks!
so much better
Hero. Your videos really help with confidence.
Thanks, appreciate the kind words 🙂
@@NeetCode I am doing leetcode like crazy, and I consider you as a mentor. Can't wait to reach one day and thank you after getting into google.
Same but by just using split on path, makes it's easier to understand
`path_arr = path.split("/")
stack = []
for sec in path_arr:
# section is not empty and section is not "." which means just current directory
if sec != '' and sec != "."
if sec == "..":
# pop previous val in stack is sec is ".."
if stack:
stack.pop()
else:
stack.append(sec)
res = "/" + "/".join(stack)
return res`
I tried something like this without having to create cur variable. There are 2 conditions - one for double dot in which case we pop from the stack if stack is not empty. The second case is for single dot - we append into our stack if dir is not equal to single dot.
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
path = path.replace('//','/')
for dir in path.split('/'):
if dir:
if dir == '..':
if stack:
stack.pop()
else:
if dir != '.':
stack.append(dir)
return '/' + '/'.join(stack)
Submission stats:
Runtime: 35 ms, faster than 84.95% of Python3 online submissions for Simplify Path.
Memory Usage: 13.9 MB, less than 37.47% of Python3 online submissions for Simplify Path.
Great explanation as always, I just listen to you explain the problem. By looking at the problem description I wasn't sure I understood all the cases.
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
path = path.split("/")
for p in path:
if stack and p == "..":
stack.pop()
if p.isalnum() or (p != "." and p != ".." and len(p) > 0):
stack.append(p)
return "/" + "/".join(stack)
Nice alternative solution 👌👌
This is the exact same solution I came up with, I think it's neater and simpler to understand
I submitted the solution provided and it was a wrong answer for the test case: "/a//b////c/d//././/..". Therefore, I have modified the solution using while inside while loop and it was accepted.
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
i = 0
while i < len(path):
if path[i] == '/':
i += 1
continue
else:
cur = ''
while i < len(path) and path[i] != '/':
cur += path[i]
i += 1
if cur == '..':
if stack:
stack.pop()
elif cur == '.' or cur == '':
i += 1
continue
else:
stack.append(cur)
return '/' + '/'.join(stack)
It'd be much simpler if you split on / and loop over the list and build your stack
"join" traverses stack in the FIFO order, but stack is a LIFO order, so I think this property should not be called "stack" or the join method should not be used with stack.
JS solution:
var simplifyPath = function(path) {
const segments=path.split("/");
const stack=[];
for (let segment of segments){
if (segment==="" || segment ===".") continue
else if (segment==="..") stack.pop()
else stack.push(segment)
}
return "/" + stack.join("/");
};
I did not need to see the code after listening to your explanation. I solved it just after listening to you.
If you go from right to left then you do not even need a stack. / and . can be handled inplace. '..' means skip one directory.
I wonder how you approach while solving the question for the first time, how do you split it into smaller part or do you immediately come with the solution at once
Thank you so much for this simple solution. My solution was too complicated and got stuck.
using two stacks was more intuitive to me for some reason
A better simple way of the solving the question
1. replace all multiple occurring slashes to single slash
2. split the string by "/"
3. now perform the stack operations on the split string array
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
while "//" in path:
path = path.replace("//","/")
splitted_string = path.split("/")
#split the string with "/" and perform opertations over the stack
for op in splitted_string:
if op=="..":
if stack:
stack.pop()
else:
continue
elif op=="." or op=="":
continue
else:
stack.append(op)
return "/"+"/".join(stack)
You always give the clearest explanations! Thanks a lot!
your explanation is so great
ur videos are just awesome
Great explanation
Why did the "/" and the end of the for loop definition make the code easier?
It helps to add the final scanned directory name to add into the stack
@@praneeth9002 how exactly is it helping?
For this specific test case:
path("/a//b////c/d//././/..") < -- realize there is a ".." at the end of this path, which means we need to pop from the top of their stack
If we didn't include the "/" in our for loop, we'll get the wrong answer. I don't like this problem since it's very tricky. But oh well.
We needed the "/" at the end of our for loop [for c in path + "/"] in order to pop the 'd'.
Thus our answer would be '/a/b/c', not 'a/b/c/d' (if you removed the '/' in the for loop)
Best way to explain it is to debug it, then you'll understand.
@@willowsongbird A simple example is take this case "/abc/def". If you don't add "/" to the end, you wouldn't add "def" to the stack, so ur ans would be "/abc", but if we add "/" to the input, our output will be "/abc/def" which is correct.
amazing explanation
Isn't modifying input a bad practice in interviews?
Context: you added a trailing "/" to the path
i think it will fail on this test case input : "/../"
Yes I agree. It fails on this test input
How can we write the last line of code in c++ instead of join
You have to use another stack , fill the new stack by popping elements of current stack . And pop each element from the new stack and make a string ans , ans += "/" + newstack->top() ;
simple solution
stack=[]
lis=path.split("/")
for items in lis:
if(items==".."):
if(stack):
stack.pop()
elif(items!="" and items!="."):
stack.append(items)
return "/"+"/".join(stack)
really neat solution. Thank you.
/I/Love/You
smooth
If this fails in leetcode, try adding cur != '..' to line 10.
This is for test cases like '/..'
it's not needed.. it'll be handled by the first if statement where we check if cur == '..'
iam shsit bro
i dont understand why you copy others solution and then try to explain them without understanding them one bit. time wasted.
I tried to do the join at the end in c# but it gave me the list in the wrong order, any idea why?
public class Solution {
public string SimplifyPath(string path) {
Stack directories = new();
StringBuilder current = new();
// /home//foo//
foreach(char character in (path + "/")){
if(character == '/'){
if(current.ToString() == ".."){
if(directories.Count > 0){
directories.Pop();
}
}
else if(current.ToString() != "" && current.ToString() != "."){
directories.Push(current.ToString());
}
current = new StringBuilder();
}
else{
current.Append(character);
}
}
// fix wrong order for return "/" + String.Join( "/", directories);
Stack answer = new();
foreach(var directory in directories){
Console.WriteLine($"directory={directory}");
answer.Push(directory);
}
return "/" + String.Join( "/", answer);
}
}
Great explanation