Simplify Path - Stack - Leetcode 71 - Python

0:00 - Read the problem
2:05 - Drawing Explanation
8:15 - Coding Explanation

leetcode 71

#stack #path #python

[yaoyao]

It's really nice that you started by explaining how the directory works. Very clear and organize video!

[danielsun]

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)

[licokr]

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!

[edwardteach]

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

[kaneknight]

Hero. Your videos really help with confidence.

[devnull]

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.

[pranavbhatia]

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.

[sahilsharma]

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`

[jagrutitiwari]

I did not need to see the code after listening to your explanation. I solved it just after listening to you.

[geekydanish]

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)

[dreamakash]

If you go from right to left then you do not even need a stack. / and . can be handled inplace. '..' means skip one directory.

[ozgeylmaz]

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

[rahatsshowcase]

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("/");
};

[curesnow]

Thank you so much for this simple solution. My solution was too complicated and got stuck.

[ehabteima]

It'd be much simpler if you split on / and loop over the list and build your stack

[kywei]

You always give the clearest explanations! Thanks a lot!

[VladPopov]

"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.

[aakankshajaiswal]

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)

[anikaboyd]

Why did the "/" and the end of the for loop definition make the code easier?

[mallepallihimasagar]

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)