Find the Shortest Superstring LeetCode solution in Rust

1
impl Solution {
2
  pub fn shortest_superstring(words: Vec<String>) -> String {
3
    let n = words.len();
4
    let mut graph = vec![vec![0; n]; n];
5
    for i in 0..n {
6
      for j in 0..n {
7
        if i != j {
8
          let mut k = words[j].len();
9
          while !words[i].ends_with(&words[j][..k]) {
10
            k -= 1;
11
          }
12
          graph[i][j] = k;
13
        }
14
      }
15
    }
16
    let mut dp = vec![vec![0; n]; 1 << n];
17
    let mut parent = vec![vec![None; n]; 1 << n];
18
    for mask in 0..1 << n {
19
      for b in 0..n {
20
        if mask >> b & 1 == 0 {
21
          continue;
22
        }
23
        let prev = mask ^ 1 << b;
24
        for (i, row) in graph.iter().enumerate() {
25
          if prev >> i & 1 == 0 {
26
            continue;
27
          }
28
          let val = dp[prev][i] + row[b];
29
          if val > dp[mask][b] {
30
            dp[mask][b] = val;
31
            parent[mask][b] = Some(i);
32
          }
33
        }
34
      }
35
    }
36
    let mut mask = (1 << n) - 1;
37
    let mut perm = Vec::with_capacity(n);
38
    let mut seen = vec![false; n];
39
    if let Some(mut p) = (0..n).max_by_key(|&i| dp[(1 << n) - 1][i]) {
40
      loop {
41
        perm.push(p);
42
        seen[p] = true;
43
        if let Some(t) = parent[mask][p] {
44
          mask ^= 1 << p;
45
          p = t;
46
        } else {
47
          break;
48
        }
49
      }
50
    }
51
    perm.extend((0..n).filter(|&i| !seen[i]));
52
    (1..perm.len())
53
      .rev()
54
      .fold(words[perm[n - 1]].clone(), |acc, i| {
55
        let overlap = graph[perm[i]][perm[i - 1]];
56
        acc + &words[perm[i - 1]][overlap..]
57
      })
58
  }
59
}