Question

Formatted question description: https://leetcode.ca/all/71.html

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.

Example 1:

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

Example 2:

Input: path = "/../"
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: path = "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Constraints:

1 <= path.length <= 3000
path consists of English letters, digits, period '.', slash '/' or '_'.
path is a valid absolute Unix path.

Algorithm

According to the example given in the title, it is really not easy to summarize the rules. Two more examples should be added path = "/a/./b/../c/", => "/a/c" and path = "/a/./b/c/", => "/a/b/c".

We can know the “.” in the middle and delete it directly, and delete it when it is “..” path next to it, and in some cases given by the following boundary conditions, it can be known that if it is empty, “/” is returned, and if there are multiple “/”, only one is retained. Then we can take the path as a number of substrings separated by one or more “/”, and extract them one by one.

Code

import java.util.Stack;

public class Simplify_Path {

	public class Solution {
	    public String simplifyPath(String path) {

	        if (path == null || path.length() == 0) {
	            return path;
	        }

	        String result = "";

	        String[] array = path.split("/");
	        Stack<String> sk = new Stack<>();

	        int i = 0;
	        while (i < array.length) {

	            if (array[i].equals("..")) {
	                if (!sk.isEmpty()) {
	                    sk.pop();
	                }
	            } else if (!array[i].equals(".") && !array[i].equals("")) {
	                sk.push(array[i]);
	            }

	            i++;
	        }

	        // @note: I missed this one
	        if (sk.isEmpty())   return "/";

	        while (!sk.isEmpty()) {
	            result = "/" + sk.pop() + result;
	        }

	        return result;
	    }
	}

}

############

class Solution {
    public String simplifyPath(String path) {
        Deque<String> stk = new ArrayDeque<>();
        for (String s : path.split("/")) {
            if ("".equals(s) || ".".equals(s)) {
                continue;
            }
            if ("..".equals(s)) {
                stk.pollLast();
            } else {
                stk.offerLast(s);
            }
        }
        return "/" + String.join("/", stk);
    }
}

// OJ: https://leetcode.com/problems/simplify-path/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    string simplifyPath(string path) {
        vector<string> v;
        istringstream ss(path);
        string s, ans;
        while (getline(ss, s, '/')) {
            if (s == "..") { 
                if (v.size()) v.pop_back();
            } else if (s.size() && s != ".") v.push_back(s);
        }
        for (auto &p : v) ans += '/' + p;
        return ans.size() ? ans : "/";
    }
};

class Solution:
    def simplifyPath(self, path: str) -> str:
        stk = []
        for s in path.split('/'):
            if not s or s == '.':
                continue
            if s == '..':
                if stk:
                    stk.pop()
            else:
                stk.append(s)
        return '/' + '/'.join(stk)

############

class Solution(object):
  def simplifyPath(self, path):
    """
    :type path: str
    :rtype: str
    """
    path = path.split("/")
    stack = []
    for p in path:
      if p in ["", "."]:
        continue
      if p == "..":
        if stack:
          stack.pop()
      else:
        stack.append(p)
    return "/" + "/".join(stack)

func simplifyPath(path string) string {
	var stk []string
	for _, s := range strings.Split(path, "/") {
		if s == "" || s == "." {
			continue
		}
		if s == ".." {
			if len(stk) > 0 {
				stk = stk[0 : len(stk)-1]
			}
		} else {
			stk = append(stk, s)
		}
	}
	return "/" + strings.Join(stk, "/")
}

function simplifyPath(path: string): string {
    // 添加辅助斜线
    path += '/';

    const stack = [];
    let str = '';
    for (let i = 1; i < path.length; i++) {
        const c = path[i];
        if (c === '/') {
            if (str !== '' && str !== '.') {
                if (str === '..') {
                    if (stack.length !== 0) {
                        stack.pop();
                    }
                } else {
                    stack.push(str);
                }
            }
            str = '';
        } else {
            str += c;
        }
    }

    return '/' + stack.join('/');
}

using System.Collections.Generic;
using System.Linq;
using System.Text;

public class Solution {
    public string SimplifyPath(string path) {
        var stack = new Stack<string>();
        var sb = new StringBuilder();
        foreach (var ch in ((IEnumerable<char>)path).Concat(Enumerable.Repeat('/', 1)))
        {
            if (ch == '/')
            {
                if (sb.Length > 0)
                {
                    var folder = sb.ToString();
                    sb.Clear();
                    switch (folder)
                    {
                        case ".":
                            break;
                        case "..":
                            if (stack.Any())
                            {
                                stack.Pop();
                            }
                            break;
                        default:
                            stack.Push(folder);
                            break;
                    }
                }
            }
            else
            {
                sb.Append(ch);
            }
        }
        
        if (stack.Count == 0)
        {
            sb.Append('/');
        }
        foreach (var folder in ((IEnumerable<string>)stack.ToList()).Reverse())
        {
            sb.Append('/');
            sb.Append(folder);
        }
        return sb.ToString();
    }
}

71 - Simplify Path

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions