C# simple DP solution with explanations. Beats 100%.
\npublic class Solution {\n    public string ShortestSuperstring(string[] words) {\n        var memo = new Dictionary<string, string>();\n        \n        // m
```\npublic class Solution {\n    public string ShortestSuperstring(string[] words) {\n        var memo = new Dictionary<string, string>();\n        \n        // mark every word as unused\n        int unused = 0;  // integer is used as a bit array\n        for(int i = 0; i < words.Length; i++) {\n            unused |= 1 << i;\n        }\n        \n        return ShortestSuperstring(words, "", unused, memo);\n    }\n    \n    private string ShortestSuperstring(string[] words, string startWord, int unused, IDictionary<string, string> memo) {\n        if (unused == 0) {\n            return startWord;\n        }\n        \n        // check memo\n        string key = startWord + "|" + unused;\n        if (memo.ContainsKey(key)) {\n            return memo[key];\n        }\n        \n        string shortest = null;\n        for(int i = 0; i < words.Length; i++) {\n            if (!IsUsed(unused, i)) {                   \n                // get the shortest superstring starting from an unused word\n                string superstring = ShortestSuperstring(words, words[i], MarkUsed(unused, i), memo);\n                \n                // "append" the shortest superstring to the start word\n                string appended = OverlapAppend(startWord, superstring);\n                \n                // keep the shortest\n                if (shortest == null || appended.Length < shortest.Length) {\n                    shortest = appended;\n                }\n            }\n        }\n        memo.Add(key, shortest);\n        return shortest;\n    }\n    \n    // "append" a to b, apply overlap. For example, "cat" and "atom" => "catom"\n    private string OverlapAppend(string a, string b) {\n        for(int i = Math.Max(1, a.Length - b.Length); i < a.Length; i++) {\n            bool match = true;\n            for(int j = i; j < a.Length; j++) {\n                if (a[j] != b[j - i]) {\n                    match = false;\n                    break;\n                }\n            }\n            \n            if (match) {\n                return a.Substring(0, i) + b;\n            }\n        }\n        return a + b;\n    }      \n    \n    private bool IsUsed(int unused, int i) {\n        return ((unused >> i) & 1) == 0;\n    }\n    \n    private int MarkUsed(int unused, int i) {\n        return unused & ~(1 << i);\n    }          \n}\n```
[]