Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Hardbitmask-dp

Find the Shortest Superstring

Problem (yeniden ifade)

n ≤ 12 tekil kelime. Her kelimeyi alt dize olarak içeren en kısa dizeyi döndür.

Sezgi

En kısa süper dize, kelimeler üzerinde bir Hamiltonian yoludur. i → j kenarının maliyeti |j| - overlap(i,j); overlap, i’nin j’nin öneki olan en uzun soneki. Başka bir kelimenin içinde kalanları önce at.

Yaklaşımlar

Örtüşme üzerinde TSP

Doğrulanmadı

Zaman O(n^2 * 2^n * L)Alan O(n * 2^n)

Fikir. dp[mask][last] = mask alt kümesinin last ile başlayan min süper dize uzunluğu. last’ı, nxt ile başlayan mask \ {last} süper dizesinin önüne yapıştır. last sonra nxt dolaş; eşit uzunlukta küçük nxt’yi tut. Tam maskede min uzunluklu başlangıçtan (eşitlikte en küçük indeks) parent yürü, artıkları yapıştır.

Yürüyüş. ["alex","loves","leetcode"] → "alexlovesleetcode". ["catg","ctaagt","gcta","ttca","atgcatc"] → "gctaagttcatgcatc".

Trade-off. Parent/eşitlik kuralları TS/PY/C#’ın aynı dizeyi üretmesi için zorunlu. n=12, 2^n n^2 yeter.

Çözüm

export function shortestSuperstring(words: string[]): string {
  const kept: string[] = [];
  for (let i = 0; i < words.length; i++) {
    const w = words[i]!;
    let contained = false;
    for (let j = 0; j < words.length; j++) {
      if (i !== j && words[j]!.includes(w)) {
        contained = true;
        break;
      }
    }
    if (!contained) kept.push(w);
  }
  words = kept;
  const n = words.length;
  if (n === 0) return "";
  const ov: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i === j) continue;
      const a = words[i]!, b = words[j]!;
      const mx = Math.min(a.length, b.length);
      for (let k = mx; k > 0; k--) {
        if (a.slice(-k) === b.slice(0, k)) {
          ov[i]![j] = k;
          break;
        }
      }
    }
  }
  const INF = 1e9;
  const N = 1 << n;
  const dp: number[][] = Array.from({ length: N }, () => new Array<number>(n).fill(INF));
  const parent: number[][] = Array.from({ length: N }, () => new Array<number>(n).fill(-1));
  for (let i = 0; i < n; i++) dp[1 << i]![i] = words[i]!.length;
  for (let mask = 0; mask < N; mask++) {
    for (let last = 0; last < n; last++) {
      if ((mask & (1 << last)) === 0) continue;
      const rest = mask ^ (1 << last);
      if (rest === 0) continue;
      for (let nxt = 0; nxt < n; nxt++) {
        if ((rest & (1 << nxt)) === 0) continue;
        const prev = dp[rest]![nxt]!;
        if (prev >= INF) continue;
        const nlen = words[last]!.length + prev - ov[last]![nxt]!;
        const p = parent[mask]![last]!;
        if (nlen < dp[mask]![last]! || (nlen === dp[mask]![last]! && (p < 0 || nxt < p))) {
          dp[mask]![last] = nlen;
          parent[mask]![last] = nxt;
        }
      }
    }
  }
  const full = N - 1;
  let best = 0;
  for (let last = 1; last < n; last++) {
    if (dp[full]![last]! < dp[full]![best]!) best = last;
  }
  const path: number[] = [];
  let mask = full, cur = best;
  while (cur >= 0) {
    path.push(cur);
    const nxt = parent[mask]![cur]!;
    mask ^= 1 << cur;
    cur = nxt;
  }
  let ans = words[path[0]!]!;
  for (let i = 1; i < path.length; i++) {
    const a = path[i - 1]!, b = path[i]!;
    ans += words[b]!.slice(ov[a]![b]!);
  }
  return ans;
}

export function shortestSuperstring(words: string[]): string {
  const kept: string[] = [];
  for (let i = 0; i < words.length; i++) {
    const w = words[i]!;
    let contained = false;
    for (let j = 0; j < words.length; j++) {
      if (i !== j && words[j]!.includes(w)) {
        contained = true;
        break;
      }
    }
    if (!contained) kept.push(w);
  }
  words = kept;
  const n = words.length;
  if (n === 0) return "";
  const ov: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i === j) continue;
      const a = words[i]!, b = words[j]!;
      const mx = Math.min(a.length, b.length);
      for (let k = mx; k > 0; k--) {
        if (a.slice(-k) === b.slice(0, k)) {
          ov[i]![j] = k;
          break;
        }
      }
    }
  }
  const INF = 1e9;
  const N = 1 << n;
  const dp: number[][] = Array.from({ length: N }, () => new Array<number>(n).fill(INF));
  const parent: number[][] = Array.from({ length: N }, () => new Array<number>(n).fill(-1));
  for (let i = 0; i < n; i++) dp[1 << i]![i] = words[i]!.length;
  for (let mask = 0; mask < N; mask++) {
    for (let last = 0; last < n; last++) {
      if ((mask & (1 << last)) === 0) continue;
      const rest = mask ^ (1 << last);
      if (rest === 0) continue;
      for (let nxt = 0; nxt < n; nxt++) {
        if ((rest & (1 << nxt)) === 0) continue;
        const prev = dp[rest]![nxt]!;
        if (prev >= INF) continue;
        const nlen = words[last]!.length + prev - ov[last]![nxt]!;
        const p = parent[mask]![last]!;
        if (nlen < dp[mask]![last]! || (nlen === dp[mask]![last]! && (p < 0 || nxt < p))) {
          dp[mask]![last] = nlen;
          parent[mask]![last] = nxt;
        }
      }
    }
  }
  const full = N - 1;
  let best = 0;
  for (let last = 1; last < n; last++) {
    if (dp[full]![last]! < dp[full]![best]!) best = last;
  }
  const path: number[] = [];
  let mask = full, cur = best;
  while (cur >= 0) {
    path.push(cur);
    const nxt = parent[mask]![cur]!;
    mask ^= 1 << cur;
    cur = nxt;
  }
  let ans = words[path[0]!]!;
  for (let i = 1; i < path.length; i++) {
    const a = path[i - 1]!, b = path[i]!;
    ans += words[b]!.slice(ov[a]![b]!);
  }
  return ans;
}

Şablon bağlantısı

Açık TSP: mask = kullanılan kelimeler, ekstra boyut = kalan yolun başlangıcı, maliyet = örtüşme sonrası uzunluk.

Yansıma

dp[mask][last] o kümenin last ile başlayan en kısa süper dizginin uzunluğu. last devamın önüne yapışır; örtüşme ek boyu kısaltır.
Örtüşme, eklenen kelimenin soneki ile devamın öneki. Kelime diğerinin içindeyse ek boy 0’a iner.
Tek kelime kendisi. Eşit uzunlukta küçük indeks parent’ta tutulur. Durum 2^n * n^2.