[Leetcode] Simplify Path 化簡路徑

liangzai_cool 發(fā)布于2019-08-14 12:40 / 3021人閱讀

摘要：棧法復(fù)雜度時間空間思路思路很簡單，先將整個路徑按照分開來，然后用一個棧，遇到時彈出一個，遇到和空字符串則不變，遇到正常路徑則壓入棧中。注意如果結(jié)果為空，要返回一個彈出棧時要先檢查棧是否為空代碼

Simplify Path

Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

棧法 復(fù)雜度

時間 O(N) 空間 O(N)

思路

思路很簡單，先將整個路徑按照/分開來，然后用一個棧，遇到..時彈出一個，遇到.和空字符串則不變，遇到正常路徑則壓入棧中。

注意

如果結(jié)果為空，要返回一個/

彈出棧時要先檢查棧是否為空

代碼

public class Solution {
    public String simplifyPath(String path) {
        Stack stk = new Stack();
        String[] parts = path.split("/");
        for(String part : parts){
            switch(part){
                case ".":
                case "" :
                    break;
                case "..":
                    if(!stk.isEmpty()){
                        stk.pop();
                    }
                    break;
                default:
                    stk.push(part);
            }
        }
        StringBuilder sb = new StringBuilder();
        if(stk.isEmpty()){
            return "/";
        }
        while(!stk.isEmpty()){
            sb.insert(0, "/"+stk.pop());
        }
        return sb.toString();
    }
}

2018/2

class Solution:
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        parts = path.split("/")
        simplified = []
        for part in parts:
            if part == "." or part == "":
                continue
            elif part == "..":
                simplified and simplified.pop()
            else:
                simplified.append(part)
        return "/" + "/".join(simplified)