Find the shortest superstring

Array String Dynamic Programming Bit Manipulation Bitmask

45.1% acceptance

Feb 25, 2026

1516

152

Given an array of strings words, return the smallest string that contains each string in words as a substring. If there are multiple valid strings of the smallest length, return any of them. You may assume that no string in words is a substring of another string in words.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn shortest_superstring(words: Vec<String>) -> String {
    let n = words.len();
    let words: Vec<Vec<u8>> = words.iter().map(|w| w.bytes().collect()).collect();
    // overlap[i][j] = how much of words[j] can be saved if preceded by words[i]
    let mut overlap = vec![vec![0usize; n]; n];
    for i in 0..n {
      for j in 0..n {
        if i == j { continue; }
        let max_ov = words[i].len().min(words[j].len());
        for ov in (0..=max_ov).rev() {
          if words[i].ends_with(&words[j][..ov]) {
            overlap[i][j] = ov;
            break;
          }
        }
      }
    }
    // dp[mask][i] = max total overlap when words in mask are used, ending at i
    let full = 1 << n;
    let mut dp = vec![vec![0i32; n]; full];
    let mut parent = vec![vec![usize::MAX; n]; full];
    for mask in 1..full {
      for last in 0..n {
        if mask & (1 << last) == 0 { continue; }
        let prev_mask = mask ^ (1 << last);
        if prev_mask == 0 { continue; }
        for prev in 0..n {
          if prev_mask & (1 << prev) == 0 { continue; }
          let val = dp[prev_mask][prev] + overlap[prev][last] as i32;
          if val > dp[mask][last] || parent[mask][last] == usize::MAX {
            dp[mask][last] = val;
            parent[mask][last] = prev;
          }
        }
      }
    }
    // Find best ending node
    let mut best_last = 0;
    for i in 1..n {
      if dp[full-1][i] > dp[full-1][best_last] { best_last = i; }
    }
    // Reconstruct path
    let mut path = Vec::new();
    let mut mask = full - 1;
    let mut cur = best_last;
    while cur != usize::MAX {
      path.push(cur);
      let prev = parent[mask][cur];
      mask ^= 1 << cur;
      cur = prev;
    }
    path.reverse();
    // Build result
    let mut result = words[path[0]].clone();
    for k in 1..path.len() {
      let ov = overlap[path[k-1]][path[k]];
      result.extend_from_slice(&words[path[k]][ov..]);
    }
    String::from_utf8(result).unwrap()
  }
}