Simplify Path

Solution For Simplify Path

Problem Statement:

Given a string path, which is an absolute path (starting with a slash ‘/’) to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period ‘.’ refers to the current directory, a double period ‘..’ refers to the directory up a level, and any multiple consecutive slashes (i.e. ‘//’) are treated as a single slash ‘/’. For this problem, any other format of periods such as ‘…’ are treated as file/directory names.

The canonical path should have the following format:

  • The path starts with a single slash ‘/’.
  • Any two directories are separated by a single slash ‘/’.
  • The path does not end with a trailing ‘/’.
  • The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period ‘.’ or double period ‘..’)

Return the simplified canonical path.

Solution:

This problem can be solved using a stack data structure. We can first split the given string path using the ‘/’ character as the delimiter. This will give us an array of directories, which we can then process one at a time.

We can use a stack to keep track of the directories that we want to keep in our simplified canonical path. We will iterate over the directories, and for each directory in the path, we will do the following:

  1. If the directory is a period ‘.’, we can ignore it as it refers to the current directory.
  2. If the directory is a double period ‘..’, we need to go up one level in the directory hierarchy. We can do this by popping the top element from the stack. If the stack is empty, we do not need to do anything as we are already at the root directory.
  3. If the directory is not a period or a double period, we can simply push it onto the stack.

After iterating over all the directories, we can pop the elements from the stack and append them to a string variable, forming the simplified canonical path.

Finally, we need to reverse the string as the stack order is in the reverse order of the path, and return the path by checking if the stack is empty or not.

Code:

class Solution:
def simplifyPath(self, path: str) -> str:
stack = [] for directory in path.split(‘/’):
if directory == ‘.’ or directory == ”:
continue
elif directory == ‘..’:
if stack:
stack.pop()
else:
stack.append(directory)
return ‘/’ + ‘/’.join(stack[::-1]) if stack else ‘/’

Step by Step Implementation For Simplify Path

/**
 * Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.

In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level. For more information, see: Absolute path vs relative path in Linux/Unix

Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.

 

Example 1:

Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.
Example 2:

Input: "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
Example 3:

Input: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
Example 4:

Input: "/a/./b/../../c/"
Output: "/c"
Example 5:

Input: "/a/../../b/../c//.//"
Output: "/c"
Example 6:

Input: "/a//b////c/d//././/.."
Output: "/a/b/c"
 */

import java.util.*;

class Solution {
    public String simplifyPath(String path) {
        // this will store the final simplified path
        StringBuilder simplifiedPath = new StringBuilder();
        
        // this is used as a stack to keep track of the directories
        // we've visited so far
        Deque stack = new ArrayDeque<>();
        
        // this array will store all the individual directories in the path
        String[] directories = path.split("/");
        
        for (String dir : directories) {
            // if the directory is empty or ".", we can simply continue
            if (dir.isEmpty() || dir.equals(".")) {
                continue;
            }
            
            // if the directory is "..", we need to backtrack
            // by popping the last directory from the stack
            if (dir.equals("..")) {
                stack.pop();
                continue;
            }
            
            // otherwise, we push the directory onto the stack
            stack.push(dir);
        }
        
        // now, we need to construct the final simplified path
        // by popping all the directories from the stack
        
        while (!stack.isEmpty()) {
            simplifiedPath.append("/");
            simplifiedPath.append(stack.pollLast());
        }
        
        // if the simplified path is empty, return "/"
        if (simplifiedPath.length() == 0) {
            return "/";
        }
        
        return simplifiedPath.toString();
    }
}
def simplifyPath(path):
        stack = []
        for p in path.split("/"):
            if p == "..":
                if stack:
                    stack.pop()
            elif p and p != ".":
                stack.append(p)
        return "/" + "/".join(stack)
var simplifyPath = function(path) {
  // your code here
};
The code should be in C++.

This is a C++ solution for the leetcode problem simplify-path:

#include 
#include 
#include 
#include 

using namespace std;

class Solution {
public:
    string simplifyPath(string path) {
        // create a stack to store the simplified path
        stack stk;
        
        // create a variable to store the current element
        string curr;
        
        // split the path by '/'
        vector v = split(path, '/');
        
        // iterate through the vector
        for (int i = 0; i < v.size(); i++) {
            // get the current element
            curr = v[i];
            
            // if the current element is "..", pop from the stack
            if (curr == "..") {
                if (!stk.empty()) {
                    stk.pop();
                }
            }
            // if the current element is ".", do nothing
            else if (curr == ".") {
                continue;
            }
            // otherwise, push the element into the stack
            else {
                stk.push(curr);
            }
        }
        
        // create a variable to store the result
        string res;
        
        // if the stack is empty, return "/"
        if (stk.empty()) {
            res = "/";
        }
        // otherwise, construct the path from the stack
        else {
            while (!stk.empty()) {
                res = "/" + stk.top() + res;
                stk.pop();
            }
        }
        
        return res;
    }
    
    // a helper function to split a string by a given delimiter
    vector split(string s, char delim) {
        // create a vector to store the result
        vector res;
        
        // create a variable to store the current element
        string curr;
        
        // iterate through the string
        for (int i = 0; i < s.length(); i++) {
            // if the current character is the delimiter
            if (s[i] == delim) {
                // if the current element is not empty, push it into the vector
                if (curr != "") {
                    res.push_back(curr);
                }
                // reset the current element
                curr = "";
            }
            // otherwise, append the character to the current element
            else {
                curr += s[i];
            }
        }
        
        // if the current element is not empty, push it into the vector
        if (curr != "") {
            res.push_back(curr);
        }
        
        return res;
    }
};
public string SimplifyPath(string path) { 
    // create a stack to store the simplified path 
    Stack stack = new Stack(); 
    
    // create a variable to store the current directory 
    string current = ""; 
    
    // loop through each character in the path 
    for(int i = 0; i < path.Length; i++) { 
        // if the character is a slash, check if the current directory is empty 
        if(path[i] == '/') { 
            // if the current directory is not empty, push it onto the stack 
            if(current != "") { 
                stack.Push(current); 
            } 
            
            // reset the current directory 
            current = ""; 
        } 
        // if the character is not a slash, append it to the current directory 
        else { 
            current += path[i]; 
        } 
    } 
    
    // if the current directory is not empty, push it onto the stack 
    if(current != "") { 
        stack.Push(current); 
    } 
    
    // create a variable to store the simplified path 
    string simplified = ""; 
    
    // while the stack is not empty, pop off the top directory and append it to the simplified path 
    while(stack.Count > 0) { 
        simplified += "/" + stack.Pop(); 
    } 
    
    // return the simplified path 
    return simplified; 
}


Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]