跳到主要内容

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

分析

很有实际价值的题目。

代码

import java.util.*;

// Simplify Path
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public String simplifyPath(String path) {
Stack<String> dirs = new Stack<>();

for (int i = 0; i < path.length();) {
++i;

int j = path.indexOf('/', i);
if (j < 0) j = path.length();
final String dir = path.substring(i, j);

// 当有连续 '///'时,dir 为空
if (!dir.isEmpty() && !dir.equals(".")) {
if (dir.equals("..")) {
if (!dirs.isEmpty())
dirs.pop();
} else {
dirs.push(dir);
}
}

i = j;
}

StringBuilder result = new StringBuilder();
if (dirs.isEmpty()) {
result.append('/');
} else {
for (final String dir : dirs) {
result.append('/').append(dir);
}
}
return result.toString();
}
}