943. Find the Shortest Superstring
leetcode hard
#array#csharp#greedy#hard#leetcode#math#search#string#tree
Task
Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.
Пример:
Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
C# solution
matched/originalpublic 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);
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public string ShortestSuperstring(vector<string> words) {
while (words.size() > 1) {
int maxOverlap = -1;
int l = 0, r = 0;
string merged = "";
for (int i = 0; i < words.size(); i++) {
for (int j = 0; j < words.size(); 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 <= min(a.size(), b.size()); i++) {
if (a.Substring(a.size() - i) == b.Substring(0, i)) {
maxOverlap = i;
}
}
return maxOverlap;
}
private string Merge(string a, string b, int overlapLen) {
return a + b.Substring(overlapLen);
}
}Java solution
matched/originalimport java.util.ArrayList;
import java.util.List;
class Solution {
public String shortestSuperstring(String[] words) {
int n = words.length;
while (n > 1) {
int maxOverlap = -1, l = 0, r = 0;
String merged = "";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
int overlapLen = overlap(words[i], words[j]);
if (overlapLen > maxOverlap) {
maxOverlap = overlapLen;
l = i;
r = j;
merged = merge(words[i], words[j], overlapLen);
}
}
}
}
words[l] = merged;
words[r] = words[n - 1];
n--;
}
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).equals(b.substring(0, i))) {
maxOverlap = i;
}
}
return maxOverlap;
}
private String merge(String a, String b, int overlapLen) {
return a + b.substring(overlapLen);
}
}JavaScript solution
matched/originalvar shortestSuperstring = function(words) {
function overlap(a, b) {
let maxOverlap = 0;
for (let i = 1; i <= Math.min(a.length, b.length); i++) {
if (a.slice(-i) === b.slice(0, i)) {
maxOverlap = i;
}
}
return maxOverlap;
}
function merge(a, b, overlapLen) {
return a + b.slice(overlapLen);
}
while (words.length > 1) {
let maxOverlap = -1;
let l = 0, r = 0;
for (let i = 0; i < words.length; i++) {
for (let j = 0; j < words.length; j++) {
if (i !== j) {
let ovlp = overlap(words[i], words[j]);
if (ovlp > maxOverlap) {
maxOverlap = ovlp;
l = i;
r = j;
}
}
}
}
words.push(merge(words[l], words[r], maxOverlap));
words.splice(r, 1);
words.splice(l, 1);
}
return words[0];
};Python solution
matched/originaldef shortestSuperstring(words):
def overlap(a, b):
max_overlap = 0
for i in range(1, min(len(a), len(b)) + 1):
if a[-i:] == b[:i]:
max_overlap = i
return max_overlap
def merge(a, b, overlap_len):
return a + b[overlap_len:]
while len(words) > 1:
max_overlap = -1
l, r = 0, 0
for i in range(len(words)):
for j in range(len(words)):
if i != j:
ovlp = overlap(words[i], words[j])
if ovlp > max_overlap:
max_overlap = ovlp
l, r = i, j
words.append(merge(words[l], words[r], max_overlap))
words.pop(r)
words.pop(l)
return words[0]Go solution
matched/originalpackage 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
}Explanation
Algorithm
Реализовать функцию overlap для вычисления максимального перекрытия двух строк, где одна строка заканчивается, а другая начинается.
Реализовать функцию merge для объединения двух строк с максимальным перекрытием.
Использовать жадный алгоритм для нахождения двух строк с максимальным перекрытием и объединить их, повторяя до тех пор, пока не останется одна строка.
Вернуть результат.
😎