The Simplify Path problem involves taking a path as a string and returning the shortest equivalent path by removing redundant elements such as ".." and ".". This problem can be solved using a variety of techniques such as string manipulation, recursion, or using a stack.
You are given a path to a file as a string. The path can contain the symbols: “..” for the parent directory and “.” for the current directory. Convert the path into its simplified form.
Input: path = "/home/../etc"
Output: "/etc"
Input: path = "/home/./me"
Output: "/home/me"
Input: path = "/home//me/"
Output: "/home/me"
Constraints
length(path)
> 0The path we are given is like any file path on your computer. The file path is made up of a series of directories separated by "/". In addition to regular directories, there are two other symbols: "." which refers to the current directory and ".." which refers to the parent directory. By following each step of the path we can find the file.
Our goal is to simplify the file path. Meaning we need to return the path in its most direct form.
Let's have a look at what simplifying a file path means with a diagram which follows an example of "/home/../etc/."
We can break down the path into a series of steps separated by "/". Starting at the root directory "/":
"home"
: go to the home directory".."
: go up one directory - which brings us back to the root directory"etc"
: go into the etc directory"."
: remain in the current directoryThe simplified path is the direct path to the file. In this case, it is "/etc". Notice how we don't include the "home" directory because we navigated out of it.
With this in mind we can divide our approach into three steps:
How can we extract a series of steps from the string? We can see that each directory is separated by a "/" or a series of "/" characters.
Extracting out each directory is then a matter of getting the substring that is in between each "/" character. Most modern programming languages provide utility functions to split a string by a delimiter.
We need to be mindful that consecutive "/" should be considered as a single directory delimiter, and there may or may not be trailing slashes.
For each directory we encounter we need to move our directory. There are three step types that we need to handle. Each of these we can identify according to the value of the directory step.
"."
: the current directory, don't change directory".."
: the parent directory, go up one directoryHow do we record what directory we are currently in? One approach would be to record the current directory as a string. Another option would be to use a stack where each item is a directory. We’ll examine each of these approaches in the solution.
Depending on the format used for tracking the current directory we may need to convert the path before returning it.
We utilize the "split" string utility function which returns an array of substrings split by a "/". This allows us to easily convert the path into a series of steps. This has the side effect of generating directories of "" when there are consecutive "/", however we can filter these out and move on to the next directory.
We also use the stack data structure to keep track of our current directory. A stack is a data structure in which items can be added to or removed from the end of the stack in constant time, and in our case the items are directories.
For each directory step, we can push when we need to move into a directory and pop when we need to navigate to the parent directory.
Let's take the example of "/home/./me/../you" and see how we can use a stack to keep track of our current directory.
We have been keeping a track of our current directory as a stack. While this is convenient for us as we have been evaluating each step, we need to return the result as a string. To convert our stack to the simplified path we can insert a "/" char in between each item in the stack and return the result.
class Solution:
def simplifyPath(self, path):
# Create the stack where we'll keep track of our current directory
pathStack = []
# 1: Convert the path string into directories
for curDir in path.split("/"):
# 2: Move directory for each path step
if not curDir:
# Consecutive "/" will result in empty directories - skip these
# Alternatively, we could filter out duplicate “/” by iterating over string before splitting it up by “/”
pass
elif curDir == ".":
# "." means don't modify current directory
pass
elif curDir == "..":
if pathStack:
# Don't pop stack if we're already at the root directory
pathStack.pop()
else:
# A "genuine" directory, navigate into it
pathStack.append(curDir)
# 3: Return the final directory
return "/" + "/".join(pathStack)
1class Solution:
2 def simplifyPath(self, path):
3 # Create the stack where we'll keep track of our current directory
4 pathStack = []
5
6 # 1: Convert the path string into directories
7 for curDir in path.split("/"):
8 # 2: Move directory for each path step
9 if not curDir:
10 # Consecutive "/" will result in empty directories - skip these
11 # Alternatively, we could filter out duplicate “/” by iterating over string before splitting it up by “/”
12 pass
13
14 elif curDir == ".":
15 # "." means don't modify current directory
16 pass
17
18 elif curDir == "..":
19 if pathStack:
20 # Don't pop stack if we're already at the root directory
21 pathStack.pop()
22
23 else:
24 # A "genuine" directory, navigate into it
25 pathStack.append(curDir)
26
27 # 3: Return the final directory
28 return "/" + "/".join(pathStack)
29
O(n)
, where n
is the number of characters in the path. Every character of the string is parsed in this solution. The stack push and pop operations take O(1)
time.O(n)
, where n is the number of directories in the path. In the worst case, the stack will only be pushed to and so will be of size O(n)
. This solution also contains the array of directories which will also be of size O(n)
.As an alternative to using a stack, we can parse the path string character by character. The current directory is also stored directly as a string rather than using a stack.
As we parse each character there are two cases. The character is a "/" or it isn't. If it isn't a "/" then it is part of a directory so we add it to our current directory string. When we encounter a "/" it means we are at the end of a directory and so we can evaluate the directory. Like before, the loop may produce empty directory strings so we need to make sure to filter those out.
The evaluation of each directory is handled in the same way as the previous method. The main difference is that we store our current directory as a string.
When we need to add a directory we can append the string to our path. When we need to go up a directory the solution is not so straightforward. We need to modify the string so that everything from and including the last "/" is removed. To do that we can locate the index of the last "/" character in the string, we can then slice the string so that everything from that index is removed.
class Solution(object):
def simplifyPath(self, path):
# Store the current directory as a string
simplifiedPath = ""
curDir = ""
# Add an ending "/" so that we always evaluate the final directory
path += "/"
for ch in path:
if ch == "/":
if not curDir:
# Consecutive "/" will result in empty directories - skip these
pass
elif curDir == ".":
# "." means don't change directory
pass
elif curDir == "..":
if simplifiedPath:
# Remove the last dir by locating the last "/" char
i = simplifiedPath.rfind("/")
simplifiedPath = simplifiedPath[:i]
else:
# A "genuine" directory, navigate into it
simplifiedPath += "/" + curDir
# Reset the directory string
curDir = ""
else:
curDir += ch
if not simplifiedPath:
# Return the root directory if the final path is empty
return "/"
return simplifiedPath
1class Solution(object):
2 def simplifyPath(self, path):
3 # Store the current directory as a string
4 simplifiedPath = ""
5 curDir = ""
6
7 # Add an ending "/" so that we always evaluate the final directory
8 path += "/"
9 for ch in path:
10 if ch == "/":
11 if not curDir:
12 # Consecutive "/" will result in empty directories - skip these
13 pass
14 elif curDir == ".":
15 # "." means don't change directory
16 pass
17 elif curDir == "..":
18 if simplifiedPath:
19 # Remove the last dir by locating the last "/" char
20 i = simplifiedPath.rfind("/")
21 simplifiedPath = simplifiedPath[:i]
22
23 else:
24 # A "genuine" directory, navigate into it
25 simplifiedPath += "/" + curDir
26
27 # Reset the directory string
28 curDir = ""
29
30 else:
31 curDir += ch
32
33 if not simplifiedPath:
34 # Return the root directory if the final path is empty
35 return "/"
36
37 return simplifiedPath
38
O(n)
, where n
is the number of characters in the path.
As in the previous solution, every character of the string is parsed. Within the loop, we are calculating the position of the last “/” character. At first glance, it appears this could make the solution O(n^2)
. However, each time we do this calculation we are only evaluating the last directory string and then removing that directory from the path. In the worst case we’d only be iterating over the entire path again. This makes the solution not as fast as the previous but in terms of time complexity it is still linear.O(1)
. Disregarding the output and input strings all the other variables have constant space. This assumes the length of a directory is much less than the size of the path itself.While both approaches have linear time complexity, the latter solution is not as fast. This is because going up one directory requires us to reparse the string which is not as fast as popping from the stack. However, the latter solution has constant space complexity because it does not require any extra memory.
Verbally noting these tradeoffs in an interview can be a great way to signal your knowledge to the interviewer.
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
Interview prep and job hunting are chaos and pain. We can help. Really.