dynamic-programming - 交织字符串 LCS

Question

嗨，我正在尝试解决交错字符串问题。这是该问题的详细说明。https://practice.geeksforgeeks.org/problems/interleaved-strings/1 我正在尝试使用 lcs 但它没有通过 leetcode 案例。这是我的代码：-（我从头到尾都使用 lcs）

class Solution {
public boolean isInterLeave(String a, String b, String c) {
                
           StringBuffer s=new StringBuffer();
            StringBuffer s1=new StringBuffer();
              StringBuffer s2=new StringBuffer();
            StringBuffer s4=new StringBuffer();
           
       int m=a.length();
        int n=c.length();
        int q=b.length();
        if(n!=m+q){
            return false;
        }
         
          LinkedHashSet<Integer> res2=  new LinkedHashSet<Integer>();
         res2= lcs(a,c,m,n);
          LinkedHashSet<Integer> res4=  new LinkedHashSet<Integer>();
         res4= lcs(b,c,q,n);
          for(int i=0;i<n;i++){
              if(res2.contains(i)==false){
                  s.append(c.charAt(i));
              }
          }
          for(int i=0;i<n;i++){
              if(res4.contains(i)==false){
                  s1.append(c.charAt(i));
              }
          }
           LinkedHashSet<Integer> res5=  new LinkedHashSet<Integer>();
         res5= LCS(a,c,m,n);
          for(int i=0;i<n;i++){
              if(res5.contains(i)==false){
                  s2.append(c.charAt(i));
              }
          } LinkedHashSet<Integer> res6=  new LinkedHashSet<Integer>();
         res6= LCS(b,c,q,n);
          for(int i=0;i<n;i++){
              if(res6.contains(i)==false){
                  s4.append(c.charAt(i));
              }
          }
          String z=s.toString();
           String u=s1.toString();
           String v=s2.toString();
           String w=s4.toString();
        
          if( (b.equals(z)==true || a.equals(u)==true) || ( b.equals(v)==true || a.equals(w)==true)){
              return true;
          }
         
         else{
             return false;
         }  
    }
        public static LinkedHashSet<Integer> lcs(String X, String Y, int m, int n)
    {
        int[][] L = new int[m+1][n+1];

        // Following steps build L[m+1][n+1] in bottom up fashion. Note
        // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]
        for (int i=0; i<=m; i++)
        {
            for (int j=0; j<=n; j++)
            {
                if (i == 0 || j == 0)
                    L[i][j] = 0;
                else if (X.charAt(i-1) == Y.charAt(j-1))
                    L[i][j] = L[i-1][j-1] + 1;
                else
                    L[i][j] = Math.max(L[i-1][j], L[i][j-1]);
            }
        }

        // Following code is used to print LCS
    
        // Create a character array to store the lcs string

 LinkedHashSet<Integer> linkedset = 
                           new LinkedHashSet<Integer>();  
        // Start from the right-most-bottom-most corner and
        // one by one store characters in lcs[]
        int i=1;
      int j=1;
        while (i <= m && j <= n)
        {
            // If current character in X[] and Y are same, then
            // current character is part of LCS
            if (X.charAt(i-1) == Y.charAt(j-1))
            {
                // Put current character in result
                
                linkedset.add(j-1);
                // reduce values of i, j and index
                i++;
                j++;
                    
            }

            // If not same, then find the larger of two and
            // go in the direction of larger value
            else if (L[i-1][j] > L[i][j-1])
                i++;
            else
                j++;
        }

    
      return linkedset;
      
    }
        public static LinkedHashSet<Integer> LCS(String X, String Y, int m, int n)
    {
        int[][] L = new int[m+1][n+1];

        // Following steps build L[m+1][n+1] in bottom up fashion. Note
        // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]
        for (int i=0; i<=m; i++)
        {
            for (int j=0; j<=n; j++)
            {
                if (i == 0 || j == 0)
                    L[i][j] = 0;
                else if (X.charAt(i-1) == Y.charAt(j-1))
                    L[i][j] = L[i-1][j-1] + 1;
                else
                    L[i][j] = Math.max(L[i-1][j], L[i][j-1]);
            }
        }

        // Following code is used to print LCS
    
        // Create a character array to store the lcs string

 LinkedHashSet<Integer> linkedset = 
                           new LinkedHashSet<Integer>();  
        // Start from the right-most-bottom-most corner and
        // one by one store characters in lcs[]
     int i = m;
        int j = n;
        while (i > 0 && j > 0)
        {
            // If current character in X[] and Y are same, then
            // current character is part of LCS
            if (X.charAt(i-1) == Y.charAt(j-1))
            {
                // Put current character in result
                linkedset.add(j-1); 
                  
                // reduce values of i, j and index
                i--; 
                j--; 
                  
            }
   
            // If not same, then find the larger of two and
            // go in the direction of larger value
            else if (L[i-1][j] > L[i][j-1])
                i--;
            else
                j--;
        }
         return linkedset;
      
    }
}

谁能建议一个 LCS 方法来解决这个问题？。我的代码没有通过以下测试用例“cacabcbaccbbcbb”-String A “acaaccaacbbbabbacc”-String B “accacaabcbacaccacacbbbbcbabbbbacc”-String C

标签： dynamic-programming

Answer 1

这将是 LCS+DP 方法。试试看：

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
    int m = s1.length(), n = s2.length();
    if (n + m != s3.length()) return false;
    if (s3.length() == 0) return true;
    
    boolean[][] dp = new boolean[m+1][n+1];
    dp[0][0] = true;
    for (int i = 0; i <= m; i++) {
        if (s1.substring(0, i).equals(s3.substring(0, i))) 
            dp[i][0] = true;
        else 
            dp[i][0] = false;
    }
    for (int j = 0; j <= n; j++) {
        if (s2.substring(0, j).equals(s3.substring(0, j))) 
            dp[0][j] = true;
        else 
            dp[0][j] = false;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)) 
                    || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1));
        }
    }
    return dp[m][n];
 }
}