字符混编

python递归解法竟然也能通过。。

class Mixture:
    def chkMixture(self, A, n, B, m, C, v):
        # write code here
        if not n+m==v:
            return False
        self.canForm=False
        self.dfs(A,B,C)
        return self.canForm
    def dfs(self,s1,s2,s3):
        if self.canForm:
            return
        if s3 == "":
            self.canForm = True
            return
        if s1 and s1[0] == s3[0]:
            self.dfs(s1[1:], s2, s3[1:])
        if s2 and s2[0] == s3[0]:
            self.dfs(s1, s2[1:], s3[1:])

class Mixture {
public:
    bool chkMixture(string A, int n, string B, int m, string C, int v) {
        if(m+n != v || v==0)
            return false;
        
        bool dp[n+1][m+1];
        dp[0][0] = true;
        
        for(int i=1;i<=n;i++)             dp[i][0] = (A[i-1]==C[i-1]);                  for(int i=1;i<=m;i++)             dp[0][i] = (B[i-1]==C[i-1]);                  for(int i=1;i<=n;i++)             for(int j=1;j<=m;j++)                 dp[i][j] = ((A[i-1]==C[i+j-1] && dp[i-1][j]) || (B[j-1]==C[i+j-1] && dp[i][j-1]));                  return dp[n][m];
    }
};

//这种题还是需要dp数组从1开始算，可省去很多边界处理问题
class Mixture {
public:

    bool chkMixture(string A, int n, string B, int m, string C, int v) {
        // write code here
        bool dp[101][101]={false};
        memset(dp,0,sizeof(bool)*101*101);
        dp[0][0] = true;
        for(unsigned int i =  1 ; i <= A.length() ;i++)
            dp[i][0] = A[i-1] == C[i-1] && dp[i-1][0];
        for(unsigned int i = 1 ; i <= B.length() ;i++)
            dp[0][i] = B[i-1] == C[i-1] && dp[0][i-1];
        
        
        for(unsigned int i = 1 ; i <= A.length() ; i++)
            {
            for(unsigned int j = 1 ; j <= B.length() ; j++)
                {
                dp[i][j] = (dp[i-1][j] && (A[i-1] == C[i+j-1])) || (dp[i][j-1] && (B[j-1] == C[i+j-1]));
                
            }
            
        }
        return dp[A.length()][B.length()];
    }
};

package 字符混编;

/**
 * Created by h on 16-12-29.
 */
//很多人写的递归根本就是错的，或者说不够优雅，正确的递归姿势应该是这样的。
public class Mixture {
    public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
        return chkMixtureHelp(A, B, C);
    }

    private boolean chkMixtureHelp(String a, String b, String c) {
        if (c.equals("") && a.equals("") && b.equals("")) return true;
        if (c.equals("")) return false;

        char ch = c.charAt(0);
        boolean ansOne = false;
        boolean ansTwo = false;

        if (a.length() > 0 && a.charAt(0) == ch) {
            ansOne = chkMixtureHelp(a.substring(1, a.length()), b, c.substring(1, c.length()));
        }
        if (b.length() > 0 && b.charAt(0) == ch) {
            ansTwo = chkMixtureHelp(a, b.substring(1, b.length()), c.substring(1, c.length()));
        }
        return ansOne || ansTwo;
    }

    public static void main(String[] args) {
        System.out.println(new Mixture().chkMixture("abaacbcababbccccbaababcbbacbaac", 31, "cacbbb", 6, "zjcrmlqwgrsocgnkvafzzeaiixzkmcyqgcmdf", 37));
    }
}

import java.util.*;
public class Mixture {
   public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
		if(n + m != v) return false;
		boolean[][] dp = new boolean[n + 1][m + 1];
		for (int i = 1; i<= n; i ++ ) if(A.charAt(i - 1) == C.charAt(i - 1)) dp[i][0] = true;
		for (int i = 1; i<= m; i ++ ) if(B.charAt(i - 1) == C.charAt(i - 1)) dp[0][i] = true;
		for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) if(C.charAt(i + j - 1) == A.charAt(i - 1) || C.charAt(i + j - 1) == B.charAt(j - 1)) dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
		return dp[n][m];
	}
}

import java.util.*;

public class Mixture {
    public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
        // write code here
        char[] a = A.toCharArray();
        char[] b = B.toCharArray();
        char[] c = C.toCharArray();
        boolean[][] dp = new boolean[a.length + 1][b.length + 1];
        dp[0][0] = true;
        for (int i = 1; i <= a.length; ++i) {
            if (a[i - 1] == c[i - 1]) {
                dp[i][0] = true;
            } else {
                break;
            }
        }
        for (int j = 1; j <= b.length; ++j) {
            if (b[j - 1] == c[j - 1]) {
                dp[0][j] = true;
            } else {
                break;
            }
        }

        for (int i = 1; i <= a.length; ++i) {
            for (int j = 1; j <= b.length; ++j) {
                if (dp[i - 1][j] && c[i + j - 1] == a[i - 1]) {
                    dp[i][j] = true;
                    continue;
                }
                if (dp[i][j - 1] && c[i + j - 1] == b[j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[a.length][b.length];
    }
}

class Mixture {
public:
    bool chkMixture(string A, int n, string B, int m, string C, int v) {
        if((n+m!=v)||(n==0&&B!=C)||(m==0&&A!=C))
            return false;
        if((n==0&&B==C)||(m==0&&A==C))
            return true;
        if(A[0]==C[0]&&B[0]!=C[0])
            return chkMixture(A.substr(1),n-1,B,m,C.substr(1),v-1);
        else if(B[0]==C[0]&&A[0]!=C[0])
            return chkMixture(A,n,B.substr(1),m-1,C.substr(1),v-1);
        else if(A[0]==C[0]&&B[0]==C[0])
            return chkMixture(A.substr(1),n-1,B,m,C.substr(1),v-1)||chkMixture(A,n,B.substr(1),m-1,C.substr(1),v-1);
        else 
            return false;
    }
};

import java.util.*;

public class Mixture {
    public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
        // write code here
        //将问题转化成最长公共子序列。设A与C的最长公共子序列长度为n1，B与C的最长公共子序列长度为n2
        //如果n1==intn，n2==intm且n1+n2==intv，则返回true，否则返回false。（借用楼上的思路java实现）
        int n1=LCS(A,C);
        int n2=LCS(B,C);
        if(n1==n&&n2==m&&n1+n2==v){
            return true;
        }else{return false;}
    }
    public int LCS(String a,String c){
        int[][] arr=new int[a.length()+1][c.length()+1];
        for(int i=0;i<a.length();i++){
            arr[i][0]=0;
        }
        for(int j=0;j<c.length();j++){
            arr[0][j]=0;
        }
        for(int i=1;i<=a.length();i++){
            for(int j=1;j<=c.length();j++){
                if(a.charAt(i-1)==c.charAt(j-1)){
                    arr[i][j]=arr[i-1][j-1]+1;
                }else {
                    if(arr[i-1][j]>=arr[i][j-1]){
                        arr[i][j]=arr[i-1][j];
                    }else{
                        arr[i][j]=arr[i][j-1];
                    }
                }
            }
        }
        return arr[a.length()][c.length()];
    }
}

class Mixture {
public:
    bool chkMixture(string A, int n, string B, int m, string C, int v) {
        // write code here
        int len1 = LCS(A, C);
        int len2 = LCS(B, C);
        return (len1==n && len2==m && v==len1+len2);
    }
    
    int LCS(string A, string B) {
        int m = A.size(), n = B.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(A[i]==B[j]) dp[i+1][j+1] = dp[i][j] + 1;
                else dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
            }
        }
        return dp[m][n];
    }
};

当遇到了A中可以和C当前匹配，B中也可以，此时不知道是和A还是和B去匹配。使用递归的方式，当遇到上面的问题的时候，会有重叠子问题，dp则没有。答案中基本上都是dp的做法，我贴以下递归的做法，本人水平有限写出来不太够优雅

class Mixture {
public:
    bool chkMixture(string A, int n, string B, int m, string C, int v) {
       if(n + m != v) return false;
       return chkMixture_recu(A, 0, n, B, 0, m, C, 0, v);
    }
    bool chkMixture_recu(string A, int pos1, int n, string B, int pos2, int m, string C, int pos3, int v) {
        if(pos1 == n && pos2 == m && pos3 == v) return true;
        if(pos1 < n && pos2 < m && pos3 < v && A[pos1] == B[pos2] && A[pos1] == C[pos3]{ return (chkMixture_recu(A, pos1 + 1, n, B, pos2, m, C, pos3 + 1, v) || chkMixture_recu(A, pos1, n, B, pos2 + 1, m, C, pos3 + 1, v));
        }else if(pos1 < n && pos3 < v && A[pos1] == C[pos3]){
            return chkMixture_recu(A, pos1 + 1, n, B, pos2, m, C, pos3 + 1, v);
        }else if(pos2 < m && pos2 < v && B[pos2] == C[pos3]) {
            return chkMixture_recu(A, pos1, n, B, pos2 + 1, m, C, pos3 + 1, v); 
        }else {
            return false;
        }
    }
};

# -*- coding:utf-8 -*-
class Mixture:
    def chkMixture(self, A, n, B, m, C, v):
        while n!=0 and m!=0 and v!=0:#某一串已遍历完
            a,b,c=A[0],B[0],C[0]
            if c==a and c==b:#A、B、C首字母相等
                return self.chkMixture(A[1:],n-1,B,m,C[1:],v-1) or self.chkMixture(A,n,B[1:],m-1,C[1:],v-1)
            elif c==a:#A、C首字母相等
                return self.chkMixture(A[1:],n-1,B,m,C[1:],v-1)
            elif c==b:#A、B首字母相等
                return self.chkMixture(A,n,B[1:],m-1,C[1:],v-1)
            else:
                return False
        return True

       public  boolean chkMixture(String A, int n, String B, int m, String C, int v) {                  if(n+m>v) return false;
                          int dp1=0;
        int dp2=0;
                 int index1=0;
        int index2=0;
                          for(int i=0;i<v&&index1<n;i++) {
            if(C.charAt(i)==A.charAt(index1)) {
                index1++;
                dp1++;
            }
        }
                 for(int i=0;i<v&&index2<m;i++) {
            if(B.charAt(index2)==C.charAt(i)) {
                index2++;
                dp2++;
            }
        }
                  //         //        System.out.println(dp1);
//        System.out.println(dp2);
                                   return dp1==n&&dp2==m;
    }

class Mixture {
public:
    bool core(string& s1,string& s2,int n,int m)
    {
        vector<vector<int>> co(n+1,vector<int>(m+1,0));
        for(int i=0;i<=n;i++)
        {
            if(s1[i]==s2[0])
                co[i][0]=1;
        }
        for(int i=0;i<=m;i++)
        {
            if(s2[i]==s1[0])
                co[0][i]=1;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(s1[i]==s2[j]) 
                {
                    co[i][j]=co[i-1][j-1]+1;
                    if(co[i][j]==m)
                        return true;
                }
                    
                  
                else
                    co[i][j]=max(co[i-1][j],co[i][j-1]);
            }
        }
        return co[n][m]==m;
    }
    bool chkMixture(string A, int n, string B, int m, string C, int v) {
        // write code here
        return core(C,A,v,n)&&core(C,B,v,m);
        
    }
};
//////////////////////////////////////////////////
class Mixture {
public:
    bool chkMixture(string A, int n, string B, int m, string C, int v) {
        // write code here
        vector<vector<bool>> co(n+1,vector<bool>(m+1,false));
        co[0][0]=true;
        for(int i=1;i<=n;i++)
        {
            if(A[i-1]==C[i-1])
                co[i][0]=true;
        }
        for(int i=1;i<=m;i++)
        {
            if(B[i-1]==C[i-1])
                co[0][i]=true;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(!co[i][j])
                {
                    if(co[i][j-1]&&(B[j-1]==C[i+j-1]))
                        co[i][j]=true;
                    if(co[i-1][j]&&(A[i-1]==C[i+j-1]))
                        co[i][j]=true;
                }
            }
        }
        return co[n][m];
    }
};