Simplify Path

Средняя№71шаг назад

Дан абсолютный путь в стиле Unix. Нужно записать его кратко: один "/" между папками, без "/" в конце, без "." (текущая папка) и без ".." (папка выше; в корне остаёмся в корне). Наш пример: "/../srv//www/./tmp/../app/" превращается в "/srv/www/app".

71 Simplify PathРазбор · 1×

Пример: "/../srv//www/./tmp/../app/", разрезанный по "/" на 10 частей; "" — пустая часть. Под ними — стек папок, в которых мы стоим, самая новая справа.

0""1..2srv3""4www5.6tmp7..8app9""folders—
ещё не прочитанаpart, читаем сейчас; только что положенная папкапрочитана, хранить нечегопапка в стекеснята из-за ".."в ответе

Начинаем с корня: в стеке ни одной папки

01/25
сначала · назад · пуск · шаг
Скорость
1function simplifyPath(path):
2 folders = empty stack
3 for each part in split(path, "/"):
4 if part is "" or part is ".":
5 continue
6 if part is "..":
7 if folders is not empty:
8 pop from folders
9 else:
10 push part onto folders
11 return "/" + join(folders, "/")
состояние
path
"/../srv//www/./tmp/../app/"
folders
[]
part
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Стек — это путь на сейчас: папки от корня до того места, где мы стоим. Зашли в папку — кладём её, а ".." выходит из папки, в которую зашли последней, то есть с верха.
  2. Пустые части и "." никуда не ведут, поэтому их пропускаем. ".." в корне снимать нечего, его тоже пропускаем: выше корня — снова корень.
  3. В стек попадают только имена папок, поэтому, склеив его через "/", получим кратчайший путь, без двойных слешей и без слеша в конце.

Сложность

Время O(n) для пути из n символов: разрезание и склейка читают его по разу, а каждую часть кладём или снимаем не больше одного раза. Память O(n) на части и стек.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.