obsidian/АиСД/Задачи/LeetCode/Simplify Path.md

Leetcode #71 | #Medium | Стек

Идея

Стек. Сплитим строку по "/", затем идем по токенам, если пустота или точка - ничего, если две точки - поднимаемся по стеку, иначе - просто кладем в стек. В конце return "/" + String.join("/", stack.reversed());

Big-O

• Время O(N)
• Память O(N)

Код

class Solution {
    public String simplifyPath(String path) {
        Deque<String> st = new ArrayDeque<>();
        for (String p : path.split("/")) {
            if (p.equals("") || p.equals(".")) continue;
            if (p.equals("..")) { if (!st.isEmpty()) st.pollLast(); }
            else st.addLast(p);
        }
        return "/" + String.join("/", st);
    }
}