Rust Dynamic Programming
The goal here is to covert the problem to the the Travelling Salesman Problem. We define and edge between 2 words as the amount of characters you need to add to
The goal here is to covert the problem to the the Travelling Salesman Problem. We define and edge between 2 words as the amount of characters you need to add to go from word1 to word2. Then we use a bitset to define which words are in the set.\n\n```\nuse std::usize;\n\n\nimpl Solution {\n    \n    fn recurse(\n        dp: &mut Vec<Vec<Option<(usize, Option<usize>)> >>, \n        edges: &Vec<Vec<usize>>,\n        set: usize,  \n        dest: usize\n    )  {\n        if dp[set][dest].is_some() {\n            return;\n        }\n        let prev_set  = set & ( !(1<<dest) );\n        let mut best = usize::MAX;\n        let mut best_i = 0; \n        \n        for i in 0..edges.len() {\n            if i == dest { continue };\n            if ((1 << i) & prev_set) == 0 { continue };\n            Self::recurse(dp, edges, prev_set, i);\n            let w = (dp[prev_set][i].as_ref().unwrap().0) + edges[i][dest];\n            if w < best {\n                best = w;\n                best_i = i;\n            }\n        }\n        dp[set][dest] = Some((best, Some(best_i)));\n    }\n    \n    pub fn shortest_superstring(mut words: Vec<String>) -> String {\n\n        let mut edges =  vec![vec![0; words.len()]; words.len()];\n                \n        for i in 0..words.len() {\n            for j in 0..words.len() {\n                if i == j { continue; }\n\n                let mut best = 0;\n                let w1 = words[i].as_bytes();\n                let w2 = words[j].as_bytes();\n                let max_overlap = w1.len().min(w2.len());\n\n                for k in (1..=max_overlap) {\n                    if w1[..k] == w2[(w2.len() - k)..] {\n                        best = k;    \n                    }\n                }\n                edges[j][i] = w1.len() - best;\n            }\n        }\n        let total_sets = (2i32.pow(words.len() as u32)) as usize;\n        let mut dp = vec![vec![None; words.len()]; total_sets];\n        let full_set = (2i32.pow((words.len()) as u32) -1) as usize;\n        for i in 0..words.len() {\n            let set = (1 << i);\n            dp[set][i] = Some((words[i].as_bytes().len(), None));\n        }\n        let mut best = (usize::MAX, None);\n        for i in 0..words.len() {\n            Self::recurse(&mut dp, &edges, full_set, i);\n            let s = (dp[full_set][i].as_ref().unwrap()).0;\n            if best.0 > s {\n                best = (s, Some(i));\n            }\n        }\n       \n        let mut order = vec![];\n        let mut cur = Some((best.1.unwrap(), full_set));\n        while let Some((index, set)) = cur {\n            order.push(index);\n            let next_set = set & (!(1<<index));\n            if let Some(&(_, o_n)) = dp[set][index].as_ref() {\n                if let Some(n) = o_n {\n                    cur = Some((n, next_set));    \n                }  else {\n                    cur = None;\n                }   \n            } else {\n                cur = None;    \n            } \n        }\n        order.reverse();\n        let mut answer = words[order[0]].clone();\n        for i in 1..(order.len()) {\n            let add = edges[order[i-1]][order[i]];\n            let size = words[order[i]].len();\n            answer.push_str(&words[order[i]][size-add..]);\n        }\n\n        \n\n        answer\n    }\n}\n```
['Dynamic Programming', 'Rust']