71. Simplify Path

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

Solution1:stack

思路: 依次push存进stack中,若..则pop
Note: 利用Deque作为stack操作时,操作都在head,pop() == removeFirst(),push() == addFirst(),所以最后遍历Deque(作为stack)时,是从stack顶到stack底,结果需要reverse, 或insert(0, str)
Time Complexity: O(N) Space Complexity: O(N)

Solution2:linkedlist

思路: 依次append存进list中,若..则removeLast
Note: 这样最后遍历Deque(作为list)时,正序即可
Time Complexity: O(N) Space Complexity: O(N)

Solution1 Code:

class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<String>();

        // to simplify the result stack by removing redundant path
        for(String str: path.split("/")) {
            if(str.equals("..")) {
                if(!stack.isEmpty()) stack.pop(); // pop() == removeFirst()
            }
            else if(str.equals(".") || str.isEmpty()) continue;
            else stack.push(str);   // push() == addFirst()
        }

        //prepare the result
        StringBuilder result = new StringBuilder("");
        for(String str: stack) result.insert(0, str).insert(0, "/");
        return result.length() == 0 ? "/": result.toString();
    }
}

Solution2 Code:

class Solution {
    public String simplifyPath(String path) {
        Deque<String> list = new LinkedList<>();

        // to simplify the result list by removing redundant path
        for(String str: path.split("/")) {
            if(str.equals("..")) {
                if(!list.isEmpty()) list.removeLast(); 
            }
            else if(str.equals(".") || str.isEmpty()) continue;
            else list.add(str);   
        }

        //prepare the result
        StringBuilder result = new StringBuilder("");
        for(String str: list) result.append("/").append(str);
        return result.length() == 0 ? "/": result.toString();
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容