Сложность: hard
Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.
Пример:
Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
👨💻 Алгоритм:
1⃣Реализовать функцию overlap для вычисления максимального перекрытия двух строк, где одна строка заканчивается, а другая начинается.
2⃣Реализовать функцию merge для объединения двух строк с максимальным перекрытием.
Использовать жадный алгоритм для нахождения двух строк с максимальным перекрытием и объединить их, повторяя до тех пор, пока не останется одна строка.
3⃣Вернуть результат.
😎 Решение:
package main
func shortestSuperstring(words []string) string {
for len(words) > 1 {
maxOverlap := -1
l, r := 0, 0
merged := ""
for i := 0; i < len(words); i++ {
for j := 0; j < len(words); j++ {
if i != j {
ovlp := overlap(words[i], words[j])
if ovlp > maxOverlap {
maxOverlap = ovlp
l = i
r = j
merged = merge(words[i], words[j], ovlp)
}
}
}
}
words[l] = merged
words = append(words[:r], words[r+1:]...)
}
return words[0]
}
func overlap(a, b string) int {
maxOverlap := 0
for i := 1; i <= min(len(a), len(b)); i++ {
if a[len(a)-i:] == b[:i] {
maxOverlap = i
}
}
return maxOverlap
}
func merge(a, b string, overlapLen int) string {
return a + b[overlapLen:]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Ставь 👍 и забирай 📚 Базу знаний