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
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.
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`
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!
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.
just had this question for google
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.
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`
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
It'd be much simpler if you split on / and loop over the list and build your stack
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.
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("/");
};
You always give the clearest explanations! Thanks a lot!
Thank you so much for this simple solution. My solution was too complicated and got stuck.
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)
ur videos are just awesome
using two stacks was more intuitive to me for some reason
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)
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.
really neat solution. Thank you.
Isn't modifying input a bad practice in interviews?
Context: you added a trailing "/" to the path
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() ;
i think it will fail on this test case input : "/../"
Yes I agree. It fails on this test input
/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);
}
}
amazing explanation
Great explanation