Почему это работает
- Стек — это путь на сейчас: папки от корня до того места, где мы стоим. Зашли в папку — кладём её, а ".." выходит из папки, в которую зашли последней, то есть с верха.
- Пустые части и "." никуда не ведут, поэтому их пропускаем. ".." в корне снимать нечего, его тоже пропускаем: выше корня — снова корень.
- В стек попадают только имена папок, поэтому, склеив его через "/", получим кратчайший путь, без двойных слешей и без слеша в конце.
Сложность
Время O(n) для пути из n символов: разрезание и склейка читают его по разу, а каждую часть кладём или снимаем не больше одного раза. Память O(n) на части и стек.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗