首页 > 试题广场 >

简化路径

[编程题]简化路径

热度指数：9618 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

请简化给出的Unix样式的文件绝对路径，也就是转换成规范路径

在Unix样式的文件系统中， .代表当前目录，.. 表示将目录向上移动一级，更多的介绍可以查看 Absolute path vs relative path in Linux/Unix

请注意，返回的规范路径必须以斜杠“/”开头，并且两个目录名之间只能有一个斜杠“/”开头。如果存在的最后一级目录的话不能以“/”结尾。另外，转化出的规范路径必须是能表示给出的绝对路径的最短字符串。

例如：

文件路径 = "/web/", =>"/web"
文件路径 = "/a/./b/../../c/", =>"/c"

特殊样例：

你有考虑过样例文件路径 ="/../"吗? 这个样例应该返回"/".
另一种特殊样例是路径中可能相邻的有多个“/”，例如“/home//web/”。这种情况下应该忽略多余的“/”，这个样例应该返回"/home/web".

示例1

输入

"/./"

输出

"/"

示例2

输入

"/.."

输出

"/"

示例3

输入

"/..."

输出

"/..."

算法知识视频讲解

LinuX18

class Solution {
public:
    string simplifyPath(string path) 
    {
     vector<string> res;
    stringstream ss(path);
    string sub;
    while(getline(ss,sub,'/'))
    {
        if(sub=="." || sub=="")
            continue;
        else if(sub==".." && res.size())
            res.pop_back();
        else if(sub != "..")
            res.push_back(sub);
    }
    string result;
    for(string temp : res)
        result += '/'+temp;
    return res.empty() ? "/" : result;  
    }
};

编辑于 2017-07-13 18:49:50 回复(2)

..Johnson

class Solution {
public:
    string simplifyPath(string path) {
        string temp, ret = "";
        vector<string> vtpath;
        for(int i = 0; i < path.length(); i ++)
            if(path[i] != '/') {
                for(temp = ""; i < path.length() && path[i] != '/'; i ++) temp += path[i];
                if(temp == ".." && vtpath.size() > 0) vtpath.pop_back();
                else if(temp != "." && temp != "..") vtpath.push_back(temp);
            }
        for(int i = 0; i < vtpath.size(); i ++) ret += "/" + vtpath[i];
        return vtpath.size() == 0? "/": ret;
    }
};

发表于 2017-10-24 17:59:59 回复(1)

元气の悟空

class Solution {
public:
    string simplifyPath(string s) {
        int i,j;
        vector<string> d;
        for(i=0;i<s.length();)
            if(s[i]!='/'){
                string tmp="";
                for(j=i;j<s.length()&&s[j]!='/';j++) tmp+=s[j];
                if(tmp!="") d.push_back(tmp);
                i=j;
            }else i++;
        int len=d.size();
        vector<int> book(len,0);
        for(i=0;i<d.size();i++)
            if(d[i]==".") book[i]=1;
            else if(d[i]==".."){
                book[i]=1;
                for(j=i;j>=0&&book[j]==1;j--);
                if(j>=0) book[j]=1;
            }
        string res="";
        for(i=0;i<len;i++)
            if(!book[i]) res+="/"+d[i];
        if(res=="") return "/";
        else return res;
    }
};

发表于 2017-10-24 17:49:16 回复(1)

潘多拉Boot

class Solution {
 public:
 /*这道题让简化给定的路径，光根据题目中给的那一个例子还真不太好总结出规律，
 应该再加上两个例子 path = "/a/./b/../c/", => "/a/c"和path = "/a/./b/c/", => "/a/b/c"， 
 这样我们就可以知道中间是"."的情况直接去掉，是".."时删掉它上面挨着的一个路径，
 而下面的边界条件给的一些情况中可以得知，如果是空的话返回"/"，如果有多个"/"只保留一个。
 那么我们可以把路径看做是由一个或多个"/"分割开的众多子字符串，把它们分别提取出来一一处理即可
 */
 string simplifyPath(string path) { 
 string res, tmp; 
 vector<string> stk; 
 stringstream ss(path); 
 while(getline(ss,tmp,'/'))   //若path="jaychou/fsw"  在while中第一次循环tmp=“jaychouao”
 //第二次循环tmp=“fsw”；
 {   if (tmp == "" || tmp == ".") 
 continue;           //是"."时候直接略过不管
 if (tmp == ".." && !stk.empty()) 
 stk.pop_back();           //是".."时删掉它上面挨着的一个路径
 else if (tmp != "..") 
 stk.push_back(tmp); 
 } 
 for(auto str : stk) 
 res += "/"+str; 
 return res.empty() ? "/" : res;
 }
 };

编辑于 2018-06-16 19:05:13 回复(0)

Java

城市里的养猫者

The main idea is to push to the stack every valid file name (not in {"",".",".."}), popping only if there's smth to pop and we met "..". I don't feel like the code below needs any additional comments.

public String simplifyPath(String path) {
    Deque<String> stack = new LinkedList<>(); Set<String> skip = new HashSet<>(Arrays.asList("..",".",""));
    for (String dir : path.split("/")) { if (dir.equals("..") && !stack.isEmpty()) stack.pop(); else if (!skip.contains(dir)) stack.push(dir);
    } String res = "";
    for (String dir : stack) res = "/" + dir + res; return res.isEmpty() ? "/" : res;
}

发表于 2017-03-12 12:05:09 回复(0)

Java

redden33

public String simplifyPath(String path) {
        Stack<String> input = new Stack<>();
        Stack<String> result = new Stack<>();
        String[] split = path.split("/");
        
        for(String s : split) if(s.length() > 0) input.push(s);    
        for(String s : input){
            if(s.equals("..")) {
                if(!result.isEmpty()) result.pop();
            }
            else if(s.equals(".")) continue;
            else result.push(s);
        }
        
        return "/" + String.join("/", result);
    }

input栈存放/之间合法的路径名，包括..和.

result栈存放识别..和.后最终的输出结果

总结：String的split()方法和join()方法能大幅简化代码，前后元素相互影响的情况下可以考虑使用栈

发表于 2019-05-18 10:59:40 回复(0)

Aphrodite_Love

import java.util.Deque;
import java.util.LinkedList;
import java.util.StringJoiner;

public class Solution {
    public static String simplifyPath(String path) {
        if (path == null || path.isEmpty() || !path.contains("/")) {
            return path;
        }
        String[] dirs = path.split("/+");
        Deque<String> stack = new LinkedList<>();
        for (String dir: dirs) {
            if(dir.isEmpty() || ".".equals(dir)) {
                continue;
            } else if ("..".equals(dir)) {
                if (!stack.isEmpty()) {
                    stack.pollLast();
                }
            } else {
                stack.offerLast(dir);
            }
        }
        
        StringJoiner stringJoiner = new StringJoiner("/", "/", "");
        while (!stack.isEmpty()) {
            stringJoiner.add(stack.pollFirst());
        }
        return stringJoiner.toString();
    }
}

发表于 2018-09-14 10:02:32 回复(0)

微软内推小王子

class Solution(object):
    def simplifyPath(self, path):
        p = []
        tokens = path.split("/")
        for t in tokens:
            if t == "." or t == "":
                continue
            elif t == "..":
                if len(p) > 0:
                    p.pop()
            else:
                p.append(t)
        return "/" + "/".join(p)

发表于 2017-10-07 19:35:15 回复(0)

C/C++

nbgao

class Solution {
public:
    string simplifyPath(string path) {
        int l = path.length();         stack<string> S;         for(int i=0;i<l;i++)          {             while(i<l && path[i]=='/')                 i++;             if(i==l)                 break;                          string t;             while(i<l && path[i]!='/')                 t += path[i++];             if(t==".")                 continue;             else if(t==".."){                 if(!S.empty())                     S.pop();             }else                 S.push(t);                      }         string result;         while(!S.empty())         {             result = '/' + S.top() + result;             S.pop();         }         if(result == "")             result = "/";         return result;
    }
};

发表于 2017-09-28 09:38:16 回复(0)

sky_

//1.遇到‘/’和'.'直接跳过
//2.遇到'..'弹出栈
//3.遇到一般的字符，压栈。
class Solution {
public:
    string simplifyPath(string path) {
            stack<string> st;
            for(int i=0;i<path.size();i++){
                while(i<path.size()&&path[i]=='/') i++;
                if(i==path.size()) break;
                string tmp;
                while(i<path.size()&&path[i]!='/') 
                      tmp+=path[i],i++;
                if(tmp==".") continue;
                else if(tmp=="..") {
                   if(st.size()) st.pop();
                   //对根目录..不做处理。
                }
                else st.push(tmp);
            }
            string ans;
            while(st.size()){
                 ans='/'+st.top()+ans;//栈底放前面
                 st.pop();
            }
            if(ans=="") ans="/";
            return ans;
    }
};

编辑于 2017-08-08 10:45:50 回复(0)

C/C++

油头教授的坩埚

C++ also have getline which acts like Java's split. I guess the code can comment itself.

string simplifyPath(string path) { string res, tmp; vector<string> stk; stringstream ss(path); while(getline(ss,tmp,'/')) { if (tmp == "" or tmp == ".") continue; if (tmp == ".." and !stk.empty()) stk.pop_back(); else if (tmp != "..") stk.push_back(tmp);
    } for(auto str : stk) res += "/"+str; return res.empty() ? "/" : res;
}

发表于 2017-03-12 12:04:36 回复(0)

老石基

import java.util.Stack;
public class Solution {
    public String simplifyPath(String path) {
        if(path==null||path.length()<=1)
    		return path;
    	Stack<Character> stack = new Stack<Character>();
    	for(int i = 0;i<path.length();i++){
    		if(path.charAt(i)=='/'){
    			if(stack.isEmpty()||stack.peek()!='/')
    				stack.add('/');
    		}else if(path.charAt(i)=='.'){
    			//判断/./
    			if(i+1<path.length()&&path.charAt(i+1)=='/'){
    				i++;
    			}else if(i+1==path.length()){
    				//判断/.
    				break;
    			}else if(i+2<path.length()&&path.substring(i, i+3).equals("../")){
    				//判断/../ 返回上一个目录
    				stack.pop();//弹出当前目录
    				while(stack.size()>1&&stack.peek()!='/')
    					stack.pop();
    				i++;
    			}else if(i+2==path.length()&&path.substring(i, i+2).equals("..")){
    				//判断/.. 返回上一个目录
    				stack.pop();//弹出当前目录
    				while(stack.size()>1&&stack.peek()!='/')
    					stack.pop();
    				i++;
    			}else{
    				while(i!=path.length()&&path.charAt(i)!='/')
    					stack.add(path.charAt(i++));
    				if(i!=path.length())
    					i--;
    			}
    		}
    		else 
				stack.add(path.charAt(i));
    	}
    	if(stack.isEmpty())
    		stack.add('/');
    	else if(stack.peek()=='/'&&stack.size()!=1)
    		stack.pop();
    	char[] result = new char[stack.size()];
    	for(int i = result.length-1;i>=0;i--){
    		result[i] = stack.pop();
    	}
        return new String(result);
    }
}

发表于 2016-06-04 17:19:18 回复(0)

丶沉梦昂志

 //来自https://www.cnblogs.com/grandyang/p/4347125.html
    public String simplifyPath(String path) {
        Stack<String> s = new Stack<>();
        String[] p = path.split("/");
        for (String t : p) {
            if (!s.isEmpty() && t.equals("..")) {
                s.pop();
            } else if (!t.equals(".") && !t.equals("") && !t.equals("..")) {
                s.push(t);
            }
        }
        List<String> list = new ArrayList<>(s);
        return "/" + String.join("/", list);//jdk8新方法String.join()
    }

发表于 2017-11-24 13:35:24 回复(1)

JavaScript

在写面经的猴子很热血

根据栈的特点实现会很方便

function simplifyPath(path) {
  const folders = [];
  const pathFolders = path.split("/").filter((folder) => folder);

  for (let folder of pathFolders) {
    if (folder === ".." || folder === "...") {
      if (folders.length > 0) {
        folders.pop();
      }
    } else if (folder !== ".") {
      folders.push(folder);
    }
  }

  return `/${folders.join("/")}`;
}

发表于 2024-05-01 10:35:36 回复(0)

C/C++

codewind

class Solution {
public:
    /**
     * 
     * @param path string字符串 
     * @return string字符串
     */
    string simplifyPath(string path) {
        // write code here
        stringstream ss(path);
        string temp;
        vector<string>res;
        while(getline(ss,temp,'/')) {
            if(temp=="." || temp=="") {
                continue;
            }else if(temp=="..") {
                if(res.size()) res.pop_back();
            }else res.push_back(temp);
        }
        if(res.empty()) return "/";
        string ans;
        for(string& x: res) {
            ans += "/" + x;
        }
        return ans;
    }
};

发表于 2021-04-11 18:15:40 回复(0)

myorange

23ms

import java.util.*;


public class Solution {
    /**
     * 
     * @param path string字符串 
     * @return string字符串
     */
    public String simplifyPath (String path) {
        if (path == null) {
            return null;
        }
        path = "/" + path;
        char[] chs = path.toCharArray();
        List<String> dir = new ArrayList<>();
        int left = 0, right = 1;
        while (right < chs.length) {
            right = left + 1;
            while(right < chs.length && chs[right] != '/') {
                right++;
            } 
            String sub = path.substring(left + 1, right);
            if (sub.equals(".") || sub.length() == 0) {
                
            } else if (sub.equals("..")) {
                if (dir.size() > 0) {
                    dir.remove(dir.size()-1);
                }
            } else {
                dir.add(sub);
            }
            left = right;
        }
        StringBuilder sb = new StringBuilder();
        for (String name : dir) {
            sb.append("/").append(name);
        }
        return dir.size() == 0 ? "/" : sb.toString();
    }
}

发表于 2021-03-10 12:55:23 回复(0)

C/C++

华科不平凡

基本思路：用vector<string> dirs存储新路径中的文件夹名称，遍历整个旧路径——

遇到/或.，忽略
遇到..，将dirs中最后一个元素推出
遇到其他字符串，推入dirs

遍历完毕后，用/连接dirs即为答案。

代码如下：

//
// Created by jt on 2020/9/25.
//
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param path string字符串
     * @return string字符串
     */
    string simplifyPath(string path) {
        // write code here
        vector<string> dirs;
        for (int i = 0; i < path.size(); ++i) {
            if (path[i] != '/') {
                int j = i;
                while (j < path.size() && path[j] != '/') ++j;
                string tmp = path.substr(i, j-i);
                i = j;
                if (tmp == ".." && !dirs.empty()) dirs.pop_back();
                if (tmp != "." && tmp != "..") dirs.push_back(tmp);
            }
        }
        string res;
        for (auto str: dirs) res += "/" + str;
        if (res.size() < 1) return "/";
        else return res;
    }
};

发表于 2020-09-25 16:11:55 回复(0)

merlinssea

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> res;
        string str="";
        int i=0;
        path = path+"/";
        while(i<path.length()){
            if(path[i]=='/'){
                if(str.length()>0){
                    if(str == ".."){
                        if(res.size()>0)
                            res.pop_back();
                    }
                    else if(str!=".")
                        res.push_back("/"+str);
                }
                str="";
            }
            else
                str=str+path[i];
            i++;
        }
        for(int i=0;i<res.size();i++){
            str+=res[i];
        }
        if(str=="")
            str = "/";
        return str;
    }
};

发表于 2020-04-22 10:27:03 回复(0)

ponmmains

import java.util.*;

public class Solution {
public String simplifyPath(String path) {
if (path == null || path.length() == 0)
return path;

List<String> list = new ArrayList<>();
String[] pathes = path.split("/");
for (String pa : pathes)
        if (!pa.equals("")) {
            switch(pa) {
case ".":
break;
case "..":
int size = list.size();
if (size != 0)
        list.remove(size - 1);
break;
default:
list.add(pa);
}
        }

StringBuilder builder = new StringBuilder();
for (String pa : list)
        builder.append("/" + pa);
String result = builder.toString();
if (result.equals(""))
result = "/";
return result;
}
}

发表于 2020-02-24 14:18:13 回复(0)

C/C++

努力的牛牛

    /*
    * 目的：简化文件绝对路径
    * 方法：使用栈
    *  1.遇到‘/’和'.'直接跳过
    *  2.遇到'..'弹出栈
    *  3.遇到一般的字符，压栈。
    */
    string simplifyPath(string path) {
        stringstream ss(path);
        string temp;
        vector<string>store;
        while(getline(ss,temp,'/')){
            if (temp=="."|| temp=="")
                continue;
            else if (temp==".." && !store.empty()){
                store.pop_back();
                continue;
            }
            else if (temp!=".."){
                store.push_back(temp);
            }
        }
        string res;
        for (auto x:store)
        {
            res+="/"+x;
        }
        res = res.empty()?"/":res;
        return res;
    }

发表于 2019-12-09 15:15:44 回复(0)