Chaîne entrelacée avec trois ou quatre chaînes

Question

J'ai implémenté le problème de la chaîne d'entrelacement avec 2 chaînes en utilisant la programmation dynamique (avec une matrice 2D) et maintenant je veux faire la même chose pour 3 ou 4 chaînes. Je n'arrive pas à comprendre comment manipuler les index. Quelqu'un peut-il m'aider à faire cela avec une matrice 3D ou 4D?

Par exemple: s1 = un, s2 = simple, s3 = exemple, res = onsimexepleample -> TRUE

MISE A JOUR ** problème de chaîne entrelacée: Étant donné trois chaînes A, B et C. C est dit être entrelacé A et B, s'il contient tous les caractères de A et B et l'ordre de tous les caractères dans les chaînes individuelles est préservé.

mise en œuvre pour deux chaînes:

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

}

Answer 1

Ok Voici mon implémentation de Java pour trois chaînes avec mémorisation de la matrice 3D:

public class Solution { 
    public boolean isInterleaving(int i, int j, int k, String s1, String s2, String s3, String S, 
      boolean dp[][][], boolean visited[][][]) { 

     if (i == s1.length() && j == s2.length() && k == s3.length()) { 
      return true; 
     } 

     if(visited[i][j][k]) { 
      return dp[i][j][k]; 
     } 

     visited[i][j][k] = true; 
     if (i < s1.length() && s1.charAt(i) == S.charAt(i + j + k)) { 
      if (isInterleaving(i + 1, j, k, s1, s2, s3, S, dp, visited)) { 
       return dp[i][j][k] = true; 
      } 
     } 

     if (j < s2.length() && s2.charAt(j) == S.charAt(i + j + k)) { 
      if (isInterleaving(i, j + 1, k, s1, s2, s3, S, dp, visited)) { 
       return dp[i][j][k] = true; 
      } 
     } 

     if (k < s3.length() && s3.charAt(k) == S.charAt(i + j + k)) { 
      if (isInterleaving(i, j, k + 1, s1, s2, s3, S, dp, visited)) { 
       return dp[i][j][k] = true; 
      } 
     } 

     return dp[i][j][k] = false; 
    } 

    public boolean isInterleave(String s1, String s2, String s3, String S) { 
     if (S.length() != s1.length() + s2.length() + s3.length()) { 
      return false; 
     } 
     boolean dp[][][] = new boolean[s1.length() + 1][s2.length() + 1][s3.length() + 1]; 
     boolean visited[][][] = new boolean[s1.length() + 1][s2.length() + 1][s3.length() + 1]; 

     return isInterleaving(0, 0, 0, s1, s2, s3, S, dp, visited); 
    } 
} 

Hope it helps! Si vous ne comprenez pas une partie, je vais mettre quelques explications :)