Greedy Solution is Wrong . Proof
Below is my solution based on a Greedy approach which got AC but when i looked into the solution where DP, BFS or TSP is used i felt that greedy might not be th
Below is my solution based on a **Greedy** approach which got **AC** but when i looked into the solution where DP, BFS or TSP is used i felt that greedy might not be the correct solution.\n\nSo after some searching found this guys comment **@Cronek** showing this testcase\n```"abcd", "bcde", "cdbc"``` . According to the greedy approach the Strings ```"abcd"``` and ```"bcde"``` will always be merged together making the final solution either to be ```"cdbcabcde"``` or ```"abcdecdbc"``` when in fact the correct solution is ```"abcdbcde"```.\n\n```\nclass Solution{\n\tpublic static class bestfit{\n\t\tprivate int index=-1;\n\t\tprivate int charmatched=-1;\n\t\tprivate int front_or_end=-1;\n\t\tbestfit(int x,int y,int z){\n\t\t\tthis.index=x;\n\t\t\tthis.charmatched=y;\n\t\t\tthis.front_or_end=z;\n\t\t}\n\t\tbestfit(int x,int y){\n\t\t\tthis(x,y,-1);\n\t\t}\n\t\tbestfit(int x){\n\t\t\tthis(x,-1,-1);\n\t\t}\n\t}\n\t\n\tpublic static String shortestSuperstring(String[] words) {\n        StringBuilder ans =new StringBuilder(words[0]);\n        int minus=1;\n        int[] marked = new int[words.length];\n        marked[0]=-1;\n        bestfit x=new bestfit(-1, -1, -1);\n        while(minus<words.length) {\n        \tString temp="";\n        \tfor(int i=0;i<marked.length;i++) {\n        \t\t\n        \t\tif(marked[i]!=-1) {\n        \t\t\ttemp=words[i];\n        \t\t\tif(x.charmatched==-1) {\n        \t\t\tx.index=i;\n        \t\t\tx.charmatched=0;\n        \t\t\tx.front_or_end=0;}\n        \t\t\t//front check \n        \t\t\tint min = temp.length()>ans.length()?ans.length():temp.length();\n        \t\t\tfor(int j=temp.length()-1;min>0;min--,j--) {\n        \t\t\t\tint charsmatched = temp.length()-j;\n        \t\t\t\tif(ans.substring(0,charsmatched).equals(temp.substring(j))) {\n        \t\t\t\t\tif(charsmatched>x.charmatched) {\n        \t\t\t\t\t\tx.index=i;\n        \t\t\t\t\t\tx.charmatched=charsmatched;\n        \t\t\t\t\t\tx.front_or_end=0;\n        \t\t\t\t\t}\n        \t\t\t\t}\n        \t\t\t}\n        \t\t\tmin = temp.length()>ans.length()?ans.length():temp.length();\n        \t\t\tfor(int j=0;min>0;j++,min--) {\n        \t\t\t\tint charsmatched = j+1;\n        \t\t\t\tif(ans.substring(ans.length()-1-j).equals(temp.substring(0,charsmatched))) {\n        \t\t\t\t\tif(charsmatched>x.charmatched) {\n        \t\t\t\t\t\tx.index=i;\n        \t\t\t\t\t\tx.charmatched=charsmatched;\n        \t\t\t\t\t\tx.front_or_end=1;\n        \t\t\t\t\t}\n        \t\t\t\t}\n        \t\t\t}\n        \t\t}\n        \t}\n        \tminus++;\n        \tmarked[x.index]=-1;\n        \ttemp=words[x.index];\n        \tif(x.front_or_end==0) {\n        \t\t//front\n        \t\tint charleft=words[x.index].length()-x.charmatched;\n        \t\tans.insert(0,temp.substring(0, charleft));\n        \t\tx.charmatched=-1;\n        \t}else{\n        \t\t//end\n//        \t\tint charused=words[x.index].length()-x.charmatched;\n        \t\tans.append(temp.substring(x.charmatched));\n        \t\tx.charmatched=-1;\n        \t}\n        }\n        return ans.toString();\n    }\n\t\n}\n```
[]