My Algorithm Summary
  • Introduction
  • Data Structure
    • Linked List
    • Stack
      • Monotone Stack
        • 42 Trapping Rain Water
        • 84 Largest Rectangle in Histogram
        • 85 Maximal Rectangle
        • 255 Verify Preorder Sequence in Binary Search Tree
        • 316 Remove Duplicate Characters
        • 402 Remove K Digits
        • 456 132 Pattern
        • 496 Next Greater Element I
        • 503 Next Greater Element II
      • 20 Valid Parentheses
      • 71 Simplify Path
      • 150 Evaluate Reverse Polish Notation
      • 155 Min Stack
      • 173 Binary Search Tree Iterator
      • 224 Basic Calculator
      • 227 Basic Calculator II
      • 232 Implement Queue using Stacks
      • 341 Flatten Nested List Iterator
      • 394 Decode String
      • 439 Ternary Expression Parser
      • 636 Exclusive Time of Functions
    • Heap
    • Trie
    • Segment Tree
    • Tree
      • 94 Binary Tree Inorder Traversal
      • 104 Maximum Depth of Binary Tree
      • 144 Binary Tree Preorder Traversal
      • 145 Binary Tree Postorder Traversal
      • 199 Binary Tree Right Side View
      • 226 Invert Binary Tree
      • 272 Closest Binary Search Tree Value II
      • 508 Most Frequent Subtree Sum
      • 513 Find Bottom Left Tree Value
      • 515 Find Largest Value in Each Tree Row
      • 617 Merge Two Binary Trees
      • 637 Average of Levels in Binary Tree
      • 653 Two Sum IV - Input is a BST
      • 654 Maximum Binary Tree
      • 669 Trim a Binary Search Tree
      • 666 Path Sum IV
      • 230 Kth Smallest Element in a BST
      • 250 Count Univalue Subtrees
      • 538 Convert BST to Greater Tree
      • 404 Sum of Left Leaves
      • 582 Kill Process
      • 112 Path Sum
      • 108 Convert Sorted Array to Binary Search Tree
      • 111 Minimum Depth of Binary Tree
      • 501 Find Mode in Binary Search Tree
      • 102 Binary Tree Level Order Traversal
      • 107 Binary Tree Level Order Traversal II
      • 103 Binary Tree Zigzag Level Order Traversal
      • 113 Path Sum II
      • 437 Path Sum III
      • 99 Recover Binary Search Tree
      • 687 Longest Univalue Path
      • 285 Inorder Successor in BST
      • 101 Symmetric Tree
      • 129 Sum Root to Leaf Numbers
      • 298 Binary Tree Longest Consecutive Sequence
      • 270 Closest Binary Search Tree Value
      • 549 Binary Tree Longest Consecutive Sequence II
      • 98 Validate Binary Search Tree
      • 652 Find Duplicate Subtrees
      • 314 Binary Tree Vertical Order Traversal
      • 333 Largest BST Subtree
      • 563 Binary Tree Tilt
      • 110 Balanced Binary Tree
    • Graph
      • Detect Cycle
  • Algorithms
    • Union Find
      • 695 Max Area of Island
      • 684 Redundant Connection
    • Binary Search
    • Topological Sorting
    • Breadth-First Search
      • 694 Number of Distinct Islands
    • Depth-First Search
    • Two Pointers
    • Sorting
    • Backtacking
    • Dynamic Programming
      • Interval DP
        • Matrix Chain Multiplication
        • Merge Stone
      • KnapSack Problem
        • 0-1 KnapSack
        • Unbounded KnapSack
      • Longest Increasing Subsequence
      • Longest Common Subsequence
    • Reservior Sampling
    • Bipartite Graph
      • Check Bipartite Graph
      • Maximal Matching - Hungarian Algorithm
    • String Pattern Matching
      • KMP Algorithm
      • Rabin Karp Algorithm
  • System Design
    • Consistent Hashing
    • Bloom Filter
    • Caching
      • LRU
      • LFU
    • Mini Twitter
    • Tiny Url
Powered by GitBook
On this page
  • 71. Simplify Path
  • 1. Question
  • 2. Implementation
  • 3. Time & Space Complexity

Was this helpful?

  1. Data Structure
  2. Stack

71 Simplify Path

Previous20 Valid ParenthesesNext150 Evaluate Reverse Polish Notation

Last updated 5 years ago

Was this helpful?

71.

1. Question

Given an absolute path for a file (Unix-style), simplify it.

For example, path="/home/", =>"/home" path="/a/./b/../../c/", =>"/c"

Corner Cases:

  • Did you consider the case where path ="/../"? In this case, you should return"/"

  • Another corner case is the path might contain multiple slashes '/'together, such as"/home//foo/"In this case, you should ignore redundant slashes and return "/home/foo".

2. Implementation

思路:根据题目的例子,我们知道" ", ".", ".."这三种情况不会出现在结果里,所以把它们存在HashSet里。如果我们遇到"..", 我们需要返回上一级目录,所以需要利用stack。最后需要将stack的结果用“/"隔开,注意stack存储结果的顺序和实际的结果是相反的。

class Solution {
    public String simplifyPath(String path) {
        Set<String> set = new HashSet<>();
        set.add(".");
        set.add("..");
        set.add("");

        Stack<String> stack = new Stack<>();

        for (String dir : path.split("/")) {
            if (dir.equals("..") && !stack.isEmpty()) {
                stack.pop();
            }
            else if (!set.contains(dir)) {
                stack.push(dir);
            }
        }

        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.insert(0, stack.pop());
            res.insert(0, "/");
        }
        return res.length() == 0 ? "/" : res.toString();
    }
}

3. Time & Space Complexity

时间和空间都是O(n)

Simplify Path