php做企业网站管理系统/网站提交入口百度

给定一个字符串数组 A，找到以 A 中每个字符串作为子字符串的最短字符串。

我们可以假设 A 中没有字符串是 A 中另一个字符串的子字符串。

示例 1：

输入：["alex","loves","leetcode"]
输出："alexlovesleetcode"
解释："alex"，"loves"，"leetcode" 的所有排列都会被接受。
示例 2：

输入：["catg","ctaagt","gcta","ttca","atgcatc"]
输出："gctaagttcatgcatc"
 

提示：

1 <= A.length <= 12
1 <= A[i].length <= 20
 

思路：状压DP。定义dp[i][j]表示状态为i时并且最后一次选择的是第j个字符串所组成的最大重叠长度。我们需要首先处理出来两个字符串间的最大重叠长度，而最短的超级串其实就是最后总的重叠长度最长。其中状态i是二进制表示的一个数，二进制的第k位为1则表示已经选择了第k个字符串。而由于最后要输出这个超级串，因此我们在找最大重叠长度的时候开一个last数组标记状态的转换路径。

class Solution {int ans;int[][] merge;String[] a;StringBuilder str;public String shortestSuperstring(String[] A) {if(A.length==1)return A[0];a=A;ans=0;int n=A.length;merge=new int[n+1][n+1];str=new StringBuilder();for(int i=0;i<n;i++)for(int j=0;j<n;j++) {if(i==j) continue;merge[i][j]=work(A[i],A[j])+1;}int[][] dp=new int[1<<n][n];int[][] last=new int[1<<n][n];for(int i=1;i<(1<<n);i++) {for(int j=0;j<n;j++) {if((i>>j&1)!=0) {int val=(i^(1<<j));if(val==0) {last[i][j]=-1;continue;}else {for(int k=0;k<n;k++) {if((val>>k&1)!=0) {if(dp[i][j]<dp[val][k]+merge[k][j]) {last[i][j]=k;dp[i][j]=dp[val][k]+merge[k][j];}}}}}}}int start=0,mx=dp[(1<<n)-1][0];Stack<Integer> st=new Stack<>();for(int i=0;i<n;i++) {if(dp[(1<<n)-1][i]>mx) {mx=dp[(1<<n)-1][i];start=i;}}int state=(1<<n)-1;while(start!=-1) {st.add(start);state^=1<<(start);start=last[state^(1<<start)][start];}int p1=st.peek();str.append(A[st.pop()]);while(!st.isEmpty()) {int p2=st.pop();str.append(A[p2].substring(merge[p1][p2]-1));p1=p2;}return str.toString();}private int work(String s1,String s2) {for(int i=0;i<s1.length();i++) {int len=s1.length()-i;if(s2.length()>=len && s1.substring(i).equals(s2.substring(0, len)))return len;}return 0;}
}