C++ | DP + Graph + BitMask with comments for understanding
\n\tclass Solution {\n\tpublic:    \n\n\t\t// cost to append word2 to word1\n\t\t// cost represents extra characters we should add after word1 so that word2 bec
\n\tclass Solution {\n\tpublic:    \n\n\t\t// cost to append word2 to word1\n\t\t// cost represents extra characters we should add after word1 so that word2 becomes suffix\n\t\tint getCost(string &word1, string &word2){\n\t\t\tint n1 = word1.size();\n\t\t\tint n2 = word2.size();\n\n\t\t\tfor(int i=0; i<n1; i++){\n\t\t\t\tint index = i;\n\t\t\t\twhile(index < n1){\n\t\t\t\t\tif(index-i >= n2 || word1[index] != word2[index-i])\n\t\t\t\t\t\tbreak;\n\t\t\t\t\tindex++;\n\t\t\t\t}\n\t\t\t\tif(index == n1){\n\t\t\t\t\treturn n2 - (n1-i);\n\t\t\t\t}\n\t\t\t}\n\n\t\t\treturn n2;\n\t\t}\n\n\n\t\tstring shortestSuperstring(vector<string>& words) {\n\t\t\tint n= words.size();\n\t\t\tstring ans="-1";\n\t\t\tint minLen = 10000;\n\n\t\t\t// graph stores the cost of appending word[j] after word[i]\n\t\t\t// cost = extra characters required to append to word[i] to get suffix word[j]\n\t\t\tvector<vector<int>> graph(n,vector<int>(n,0));\n\t\t\tfor(int i=0; i<n; i++){\n\t\t\t\tfor(int j=0; j<n; j++){\n\t\t\t\t\tgraph[i][j] = getCost(words[i],words[j]);\n\t\t\t\t}\n\t\t\t}\n\n\t\t\t// bits of mask stores which words have been used, in the end all are used \n\t\t\t// 111111111... n times\n\t\t\tint mask_end= (1<<n) -1; \n\n\t\t\t// dp[mask][j] stores shortest superstring till now using set bits of mask\n\t\t\t// and containing ending word as words[j] \n\t\t\t// if we remove the jth bit from current mask, we get previous mask \n\t\t\t// in previous mask there are n possibilities of ending words\n\t\t\tvector<vector<pair<int,string>>> dp(mask_end+1, \n\t\t\t\t\t\t\t\t\t\t\t\tvector<pair<int,string>>(n,{10000,""}));\n\n\t\t\tfor(int mask=0; mask<= mask_end; mask++){\n\t\t\t\t// get all possible prevMask\n\t\t\t\tfor(int j=0; j<n; j++){\n\t\t\t\t\t// if jth bit of mask is set, means jth word is used \n\t\t\t\t\tif(mask && (1<<j) != 0){\n\t\t\t\t\t\t// remove jth bit from mask\n\t\t\t\t\t\tint preMask = mask ^ (1<<j);\n\t\t\t\t\t\t// if j is the first word\n\t\t\t\t\t\tif(preMask ==0)\n\t\t\t\t\t\t\tdp[mask][j] = {words[j].size(), words[j]};\n\t\t\t\t\t\telse{\n\t\t\t\t\t\t\t// check all possible ending words from preMask \n\t\t\t\t\t\t\t// ie.previous state from which current state (mask) is formed\n\t\t\t\t\t\t\tint kmin= -1;\n\t\t\t\t\t\t\tint minCurrLen = dp[mask][j].first;\n\t\t\t\t\t\t\tfor(int k=0; k<n; k++){\n\t\t\t\t\t\t\t\tint preLen = dp[preMask][k].first;\n\t\t\t\t\t\t\t\tif(preLen + graph[k][j] < minCurrLen){\n\t\t\t\t\t\t\t\t\tminCurrLen = preLen + graph[k][j];\n\t\t\t\t\t\t\t\t\tkmin= k;\n\t\t\t\t\t\t\t\t}\n\t\t\t\t\t\t\t}  \n\t\t\t\t\t\t\tif(kmin != -1){\n\t\t\t\t\t\t\t\tstring preStr = dp[preMask][kmin].second;\n\t\t\t\t\t\t\t\t// add graph[kmin][j] end letters of words[j] to preStr\n\t\t\t\t\tpreStr += words[j].substr(words[j].size()- graph[kmin][j], graph[kmin][j]);\n\t\t\t\t\t\t\t\tdp[mask][j] = {minCurrLen,preStr};\n\t\t\t\t\t\t\t}\n\t\t\t\t\t\t}\n\t\t\t\t\t}\n\n\t\t\t\t\tif(mask == mask_end && dp[mask][j].first < minLen){\n\t\t\t\t\t\tminLen = dp[mask][j].first;\n\t\t\t\t\t\tans = dp[mask][j].second;\n\t\t\t\t\t}\n\n\t\t\t\t}\n\t\t\t}\n\n\t\t\treturn ans;\n\n\n\t\t}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\t};
[]