Ежедневные задачи LeetCode: Задача 71 Упрощение пути

LeetCode - это популярная онлайн-платформа, которая предлагает большую коллекцию задач и проблем по кодированию, чтобы помочь инженерам-программистам и разработчикам улучшить свои навыки кодирования и подготовиться к техническим собеседованиям. В этой статье мы обсудим задачу LeetCode номер 71, которая называется "Упростить путь", и предложим подход к ее решению.

Постановка задачи:

Задав строку path, которая является абсолютным путем (начинающимся со слэша '/') к файлу или каталогу в файловой системе Unix-стиля, преобразовать ее в упрощенный канонический путь.

В файловой системе Unix точка '.' относится к текущему каталогу, двойная точка '.' относится к каталогу на уровень выше, а любые несколько последовательных косых черт (например, '//') рассматриваются как одна косая черта '/'. Для данной задачи любой другой формат периодов, например "...", не допускается.

Подход:

Задача требует упростить заданный абсолютный путь до канонического пути, используя правила в стиле Unix. Мы можем сделать это, итерируя каждый компонент входного пути и обрабатывая его соответствующим образом.

Мы можем использовать структуру данных stack для отслеживания каталогов в каноническом пути. Мы помещаем каталоги в стек, когда встречаем их в пути, и вынимаем каталоги из стека, когда встречаем компонент '.'.

Главное - правильно обрабатывать различные компоненты пути:

• Если мы встречаем одинарный период '.', мы можем игнорировать его, поскольку он относится к текущему каталогу.
• Если мы встречаем двойной период '.', нам нужно удалить последний каталог из стека, так как он ссылается на родительский каталог.
• Если мы встречаем имя каталога, мы просто помещаем его в стек.

После обработки всех компонентов входного пути мы можем построить упрощенный канонический путь, извлекая каталоги из стека в обратном порядке и объединяя их разделителем '/'. Мы должны быть внимательны, чтобы добавить ведущее '/' к конечному пути, как того требует постановка задачи.

Псевдокод:

1. Initialize a stack to hold the directories
2. Split the input path by '/'
3. For each component of the path:
    a. If the component is empty or '.', ignore it
    b. If the component is '..', pop the top directory from the stack if it's not empty
    c. Otherwise, push the component onto the stack
4. Construct the canonical path by popping the directories off the stack in reverse order
   and concatenating them with a '/' separator
5. If the stack is empty, return '/'
   otherwise, return the constructed path with a leading '/'

Анализ сложности

Временная сложность этого подхода составляет O(n), где n - длина входного пути. Мы выполняем итерации над каждым компонентом пути ровно один раз.

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

Решение

C++

class Solution {
 public:
  string simplifyPath(string path) {
    string ans;
    istringstream iss(path);
    vector<string> stack;

    for (string dir; getline(iss, dir, '/');) {
      if (dir.empty() || dir == ".")
        continue;
      if (dir == "..") {
        if (!stack.empty())
          stack.pop_back();
      } else {
        stack.push_back(dir);
      }
    }

    for (const string& s : stack)
      ans += "/" + s;

    return ans.empty() ? "/" : ans;
  }
};

Что делает этот код:

1. Инициализируется пустая строковая переменная ans для хранения конечного результата.
2. Создается объект istringstream iss, инициализированный входным путем.
3. Создается пустой вектор<string> под названием stack для хранения каталогов в каноническом пути.
4. Он использует цикл for и функцию getline для разбиения строки пути на компоненты, разделенные символом '/'.
5. Для каждого компонента проверяется, пуст ли он или равен "." (текущий каталог), в этом случае он пропускается.
6. Если компонент равен "." (родительский каталог), проверяется, не пуст ли стек, и выгружается последний каталог из стека.
7. В противном случае он добавляет каталог в стек.
8. После обработки всех компонентов используется еще один цикл for для итерации по стеку и построения строки ans путем конкатенации каждого каталога с ведущим разделителем "/".
9. Если строка ans пуста, она устанавливает значение "/", как того требует постановка задачи.
10. Он возвращает конечную строку ans, которая представляет собой упрощенный канонический путь.

Время выполнения: 7 мс, память: 9,5 МБ

Java

class Solution {
  public String simplifyPath(String path) {
    final String[] dirs = path.split("/");
    Stack<String> stack = new Stack<>();

    for (final String dir : dirs) {
      if (dir.isEmpty() || dir.equals("."))
        continue;
      if (dir.equals("..")) {
        if (!stack.isEmpty())
          stack.pop();
      } else {
        stack.push(dir);
      }
    }

    return "/" + String.join("/", stack);
  }
}

Что делает этот код:

1. Инициализирует строковый массив dirs путем разбиения входного пути на компоненты с использованием символа "/" в качестве разделителя.
2. Он создает новый стек объектов Stack<String> для хранения каталогов в каноническом пути.
3. Он использует цикл for-each для перебора каждого каталога в dirs.
4. Для каждой директории проверяется, пуста ли она или равна "." (текущая директория), в этом случае она пропускается.
5. Если каталог равен "." (родительский каталог), проверяется, не пуст ли стек, и выгружается последний каталог из стека.
6. В противном случае каталог добавляется в стек.
7. После обработки всех каталогов он формирует конечный результат, объединяя элементы стека с разделителем "/" с помощью метода String.join() и добавляя ведущий символ "/", как того требует постановка задачи.
8. Возвращается конечная строка, представляющая упрощенный канонический путь.

Время выполнения: 5 мс, Память: 42,5 МБ

Python

class Solution:
  def simplifyPath(self, path: str) -> str:
    stack = []

    for str in path.split('/'):
      if str in ('', '.'):
        continue
      if str == '..':
        if stack:
          stack.pop()
      else:
        stack.append(str)

    return '/' + '/'.join(stack)

Вот что она делает:

1. Инициализирует пустой стек списков для хранения каталогов в каноническом пути.
2. Он использует цикл for и метод split для разделения строки пути на компоненты, разделенные символом '/'.
3. Для каждого компонента проверяется, пуст ли он или равен "." (текущий каталог), в этом случае он пропускается.
4. Если компонент равен "." (родительский каталог), проверяется, не пуст ли стек, и выгружается последний каталог из стека.
5. В противном случае каталог добавляется в стек.
6. После обработки всех компонентов он формирует конечный результат, объединяя элементы стека с разделителем "/" с помощью метода join и добавляя ведущий символ "/", как того требует постановка задачи.
7. Он возвращает конечную строку, которая представляет собой упрощенный канонический путь.

Время выполнения: 37 мс, память: 13,8 МБ

Заключение:

В этой статье мы обсудили проблему 71 LeetCode: "Упростить путь". Мы описали подход, использующий структуру данных стека для упрощения заданного абсолютного пути до канонического пути с использованием правил в стиле Unix. Мы представили псевдокод и анализ сложности подхода. Эта задача может стать хорошим упражнением для отработки манипуляций со строками и стеком.

Посмотрите мой репозиторий Github для решений около 350 задач LeetCode на разных языках программирования, а также проверьте мой аккаунт LeetCode здесь.