Сложность: hard
Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.
Пример:
Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
👨💻 Алгоритм:
1⃣Реализовать функцию overlap для вычисления максимального перекрытия двух строк, где одна строка заканчивается, а другая начинается.
2⃣Реализовать функцию merge для объединения двух строк с максимальным перекрытием.
Использовать жадный алгоритм для нахождения двух строк с максимальным перекрытием и объединить их, повторяя до тех пор, пока не останется одна строка.
3⃣Вернуть результат.
😎 Решение:
public class Solution {
public string ShortestSuperstring(string[] words) {
while (words.Length > 1) {
int maxOverlap = -1;
int l = 0, r = 0;
string merged = "";
for (int i = 0; i < words.Length; i++) {
for (int j = 0; j < words.Length; j++) {
if (i != j) {
int 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 = words.Where((val, idx) => idx != r).ToArray();
}
return words[0];
}
private int Overlap(string a, string b) {
int maxOverlap = 0;
for (int i = 1; i <= Math.Min(a.Length, b.Length); i++) {
if (a.Substring(a.Length - i) == b.Substring(0, i)) {
maxOverlap = i;
}
}
return maxOverlap;
}
private string Merge(string a, string b, int overlapLen) {
return a + b.Substring(overlapLen);
}
}Ставь 👍 и забирай 📚 Базу знаний