Сегодня мы решим 6-ю задачу мартовского конкурса LeetCoding Challenge.

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

Действительная кодировка массива words — это любая ссылочная строка s и массив индексов indices, такие что:

  • words.length == indices.length
  • Ссылочная строка s заканчивается символом '#'.
  • Для каждого индекса indices[i] подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включая) следующим символом '#', равна words[i].

Учитывая массив words, вернуть длину кратчайшей ссылочной строкиsиз возможных допустимых кодировокwords .

Пример 1:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

Пример 2:

Input: words = ["t"]
Output: 2
Explanation: A valid encoding would be s = "t#" and indices = [0].

Ограничения:

  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 7
  • words[i] состоит только из строчных букв.

Решение

Согласно вопросу, мы должны закодировать заданные строки в одну строку, содержащую все слова из заданного массива строк. Это должно быть сделано таким образом, чтобы мы могли минимизировать длину выходной строки. Допускается наложение одной строки на другую. Также после каждой строки мы должны добавить к ней #.

Пройдемся по алгоритму решения этой задачи. Здесь мы использовали Hashset для сохранения всех заданных строк. Мы проверим перекрытие символов слов, если есть какое-либо перекрытие символов, мы удалим эту строку. (Этот шаг можно лучше понять на примере). Наконец, мы присоединяем строки, присутствующие в Hashset, и добавляем к нему #.

Код приведен ниже.

Если n — длина массива строк, а k — длина самой длинной строки, то

Временная сложность: O(n*k)

Пространственная сложность: O(n)

Код можно найти в следующем репозитории.



sksaikia/LeetCode
Внесите свой вклад в разработку sksaikia/LeetCode, создав учетную запись на GitHub.github.com



Я опубликовал все предыдущие задачи для мартовского конкурса LeetCoding Challenge 2021. Вы можете с ними ознакомиться.

  1. Мартовское соревнование LeetCoding — День 1 — Раздача конфет
  2. Мартовское соревнование LeetCoding — День 2 — Несоответствие наборов
  3. Мартовский вызов LeetCoding — день 3 — пропущенный номер
  4. Мартовский вызов LeetCoding — День 4 — Пересечение двух связанных списков
  5. Мартовское соревнование LeetCoding — День 5 — Среднее количество уровней в двоичном дереве