Simplify Path

描述

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".

分析

很有实际价值的题目。

代码

  1. import java.util.*;
  3. // Simplify Path
  4. // 时间复杂度O(n)，空间复杂度O(n)
  5. class Solution {
  6.     public String simplifyPath(String path) {
  7.         Stack<String> dirs = new Stack<>();
  9.         for (int i = 0; i < path.length();) {
  10.             ++i;
  12.             int j = path.indexOf('/', i);
  13.             if (j < 0) j = path.length();
  14.             final String dir = path.substring(i, j);
  16.             // 当有连续 '///'时，dir 为空
  17.             if (!dir.isEmpty() && !dir.equals(".")) {
  18.                 if (dir.equals("..")) {
  19.                     if (!dirs.isEmpty())
  20.                         dirs.pop();
  21.                 } else {
  22.                     dirs.push(dir);
  23.                 }
  24.             }
  26.             i = j;
  27.         }
  29.         StringBuilder result = new StringBuilder();
  30.         if (dirs.isEmpty()) {
  31.             result.append('/');
  32.         } else {
  33.             for (final String dir : dirs) {
  34.                 result.append('/').append(dir);
  35.             }
  36.         }
  37.         return result.toString();
  38.     }
  39. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/string/simplify-path.html