欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 71. Simplify Path(Unix下简化路径)

程序员文章站 2022-05-22 15:04:04
...

算法思路:
首先设置一个String类型的栈。用spilt方法,对path进行分割,以“/”为分隔符分割得到一组字符串。接着遍历这组字符串,遇到空字符串(“”)和当前目录(".")跳过,若字符串为".."且栈不为空时弹栈,若字符串为".."且栈为空则跳过,其他情况则将元素压栈(if…else if…else…)。最后将栈中的元素和"/"按顺序组合成一条有效路径,当路径为空时,返回根目录,否则返回路径。

该算法时间复杂度O(n),空间复杂度(n)。参考代码:

//leetcode 71. Simplify Path
    public static String simplifyPath(String path) {
    	Stack<String> stack = new Stack<String>();
        String[] tokens = path.split("/");
        for(int i=0;i<tokens.length;i++){
        	if(tokens[i].equals("")||tokens[i].equals("."))
        		continue;
        	if(tokens[i].equals("..")&&!stack.isEmpty()){
        		stack.pop();
        	}else if(tokens[i].equals("..")&&stack.isEmpty()){
        		continue;
        	}else{
        		stack.push(tokens[i]);
        	}
        }
        StringBuilder s = new StringBuilder("");
        while(!stack.isEmpty()){
        	String str = "/"+stack.pop();
        	s.insert(0, str);
        }
        if(s.length()==0)
        	return "/";
    	return s.toString();
    }
相关标签: Stack