Dadas tres strings A, B y C. Escriba una función que verifique si C es un entrelazado de A y B. Se dice que C está entrelazando A y B, si contiene todos y solo los caracteres de A y B y el orden de todos los caracteres en strings individuales se conserva.
Ejemplo:
C
// A simple recursive function to check
// whether C is an interleaving of A and B
bool isInterleaved(
char* A, char* B, char* C)
{
// Base Case: If all strings are empty
if (!(*A || *B || *C))
return true;
// If C is empty and any of the
// two strings is not empty
if (*C == '\0')
return false;
// If any of the above mentioned
// two possibilities is true,
// then return true, otherwise false
return ((*C == *A) && isInterleaved(
A + 1, B, C + 1))
|| ((*C == *B) && isInterleaved(
A, B + 1, C + 1));
}
C++
// A Dynamic Programming based program
// to check whether a string C is
// an interleaving of two other
// strings A and B.
#include <iostream>
#include <string.h>
using namespace std;
// The main function that
// returns true if C is
// an interleaving of A
// and B, otherwise false.
bool isInterleaved(
char* A, char* B, char* C)
{
// Find lengths of the two strings
int M = strlen(A), N = strlen(B);
// Let us create a 2D table
// to store solutions of
// subproblems. C[i][j] will
// be true if C[0..i+j-1]
// is an interleaving of
// A[0..i-1] and B[0..j-1].
bool IL[M + 1][N + 1];
// Initialize all values as false.
memset(IL, 0, sizeof(IL));
// C can be an interleaving of
// A and B only of the sum
// of lengths of A & B is equal
// to the length of C.
if ((M + N) != strlen(C))
return false;
// Process all characters of A and B
for (int i = 0; i <= M; ++i) {
for (int j = 0; j <= N; ++j) {
// two empty strings have an
// empty string as interleaving
if (i == 0 && j == 0)
IL[i][j] = true;
// A is empty
else if (i == 0) {
if (B[j - 1] == C[j - 1])
IL[i][j] = IL[i][j - 1];
}
// B is empty
else if (j == 0) {
if (A[i - 1] == C[i - 1])
IL[i][j] = IL[i - 1][j];
}
// Current character of C matches
// with current character of A,
// but doesn't match with current
// character of B
else if (
A[i - 1] == C[i + j - 1]
&& B[j - 1] != C[i + j - 1])
IL[i][j] = IL[i - 1][j];
// Current character of C matches
// with current character of B,
// but doesn't match with current
// character of A
else if (
A[i - 1] != C[i + j - 1]
&& B[j - 1] == C[i + j - 1])
IL[i][j] = IL[i][j - 1];
// Current character of C matches
// with that of both A and B
else if (
A[i - 1] == C[i + j - 1]
&& B[j - 1] == C[i + j - 1])
IL[i][j]
= (IL[i - 1][j]
|| IL[i][j - 1]);
}
}
return IL[M][N];
}
// A function to run test cases
void test(char* A, char* B, char* C)
{
if (isInterleaved(A, B, C))
cout << C << " is interleaved of "
<< A << " and " << B << endl;
else
cout << C << " is not interleaved of "
<< A << " and " << B << endl;
}
// Driver program to test above functions
int main()
{
test("XXY", "XXZ", "XXZXXXY");
test("XY", "WZ", "WZXY");
test("XY", "X", "XXY");
test("YX", "X", "XXY");
test("XXY", "XXZ", "XXXXZY");
return 0;
}
Java
// A Dynamic Programming based program
// to check whether a string C is
// an interleaving of two other
// strings A and B.
import java.io.*;
import java.util.*;
import java.lang.*;
class GFG{
// The main function that returns
// true if C is an interleaving of A
// and B, otherwise false.
static boolean isInterleaved(String A, String B,
String C)
{
// Find lengths of the two strings
int M = A.length(), N = B.length();
// Let us create a 2D table to store
// solutions of subproblems. C[i][j]
// will be true if C[0..i+j-1] is an
// interleaving of A[0..i-1] and B[0..j-1].
boolean IL[][] = new boolean[M + 1][N + 1];
// IL is default initialised by false
// C can be an interleaving of A and B
// only if the sum of lengths of A and B
// is equal to length of C
if ((M + N) != C.length())
return false;
// Process all characters of A and B
for(int i = 0; i <= M; i++)
{
for(int j = 0; j <= N; j++)
{
// Two empty strings have an
// empty strings as interleaving
if (i == 0 && j == 0)
IL[i][j] = true;
// A is empty
else if (i == 0)
{
if (B.charAt(j - 1) ==
C.charAt(j - 1))
IL[i][j] = IL[i][j - 1];
}
// B is empty
else if (j == 0)
{
if (A.charAt(i - 1) ==
C.charAt(i - 1))
IL[i][j] = IL[i - 1][j];
}
// Current character of C matches
// with current character of A,
// but doesn't match with current
// character if B
else if (A.charAt(i - 1) ==
C.charAt(i + j - 1) &&
B.charAt(j - 1) !=
C.charAt(i + j - 1))
IL[i][j] = IL[i - 1][j];
// Current character of C matches
// with current character of B, but
// doesn't match with current
// character if A
else if (A.charAt(i - 1) !=
C.charAt(i + j - 1) &&
B.charAt(j - 1) ==
C.charAt(i + j - 1))
IL[i][j] = IL[i][j - 1];
// Current character of C matches
// with that of both A and B
else if (A.charAt(i - 1) ==
C.charAt(i + j - 1) &&
B.charAt(j - 1) ==
C.charAt(i + j - 1))
IL[i][j] = (IL[i - 1][j] ||
IL[i][j - 1]);
}
}
return IL[M][N];
}
// Function to run test cases
static void test(String A, String B, String C)
{
if (isInterleaved(A, B, C))
System.out.println(C + " is interleaved of " +
A + " and " + B);
else
System.out.println(C + " is not interleaved of " +
A + " and " + B);
}
// Driver code
public static void main(String[] args)
{
test("XXY", "XXZ", "XXZXXXY");
test("XY", "WZ", "WZXY");
test("XY", "X", "XXY");
test("YX", "X", "XXY");
test("XXY", "XXZ", "XXXXZY");
}
}
// This code is contributed by th_aditi
Python3
# A Dynamic Programming based python3 program
# to check whether a string C is an interleaving
# of two other strings A and B.
# The main function that returns true if C is
# an interleaving of A and B, otherwise false.
def isInterleaved(A, B, C):
# Find lengths of the two strings
M = len(A)
N = len(B)
# Let us create a 2D table to store solutions of
# subproblems. C[i][j] will be true if C[0..i + j-1]
# is an interleaving of A[0..i-1] and B[0..j-1].
# Initialize all values as false.
IL = [[False] * (N + 1) for i in range(M + 1)]
# C can be an interleaving of A and B only of sum
# of lengths of A & B is equal to length of C.
if ((M + N) != len(C)):
return False
# Process all characters of A and B
for i in range(0, M + 1):
for j in range(0, N + 1):
# two empty strings have an empty string
# as interleaving
if (i == 0 and j == 0):
IL[i][j] = True
# A is empty
elif (i == 0):
if (B[j - 1] == C[j - 1]):
IL[i][j] = IL[i][j - 1]
# B is empty
elif (j == 0):
if (A[i - 1] == C[i - 1]):
IL[i][j] = IL[i - 1][j]
# Current character of C matches with
# current character of A, but doesn't match
# with current character of B
elif (A[i - 1] == C[i + j - 1] and
B[j - 1] != C[i + j - 1]):
IL[i][j] = IL[i - 1][j]
# Current character of C matches with
# current character of B, but doesn't match
# with current character of A
elif (A[i - 1] != C[i + j - 1] and
B[j - 1] == C[i + j - 1]):
IL[i][j] = IL[i][j - 1]
# Current character of C matches with
# that of both A and B
elif (A[i - 1] == C[i + j - 1] and
B[j - 1] == C[i + j - 1]):
IL[i][j] = (IL[i - 1][j] or IL[i][j - 1])
return IL[M][N]
# A function to run test cases
def test(A, B, C):
if (isInterleaved(A, B, C)):
print(C, "is interleaved of", A, "and", B)
else:
print(C, "is not interleaved of", A, "and", B)
# Driver Code
if __name__ == '__main__':
test("XXY", "XXZ", "XXZXXXY")
test("XY", "WZ", "WZXY")
test("XY", "X", "XXY")
test("YX", "X", "XXY")
test("XXY", "XXZ", "XXXXZY")
# This code is contributed by ashutosh450
C#
// A Dynamic Programming based program
// to check whether a string C is
// an interleaving of two other
// strings A and B.
using System;
class GFG
{
// The main function that returns
// true if C is an interleaving of A
// and B, otherwise false.
static bool isInterleaved(string A, string B,
string C)
{
// Find lengths of the two strings
int M = A.Length, N = B.Length;
// Let us create a 2D table to store
// solutions of subproblems. C[i][j]
// will be true if C[0..i+j-1] is an
// interleaving of A[0..i-1] and B[0..j-1].
bool[ , ] IL = new bool[M + 1, N + 1];
// IL is default initialised by false
// C can be an interleaving of A and B
// only if the sum of lengths of A and B
// is equal to length of C
if ((M + N) != C.Length)
return false;
// Process all characters of A and B
for(int i = 0; i <= M; i++)
{
for(int j = 0; j <= N; j++)
{
// Two empty strings have an
// empty strings as interleaving
if (i == 0 && j == 0)
IL[i, j] = true;
// A is empty
else if (i == 0)
{
if (B[j - 1] == C[j - 1])
IL[i, j] = IL[i, j - 1];
}
// B is empty
else if (j == 0)
{
if (A[i - 1] == C[i - 1])
IL[i, j] = IL[i - 1, j];
}
// Current character of C matches
// with current character of A,
// but doesn't match with current
// character if B
else if (A[i - 1] == C[i + j - 1] &&
B[j - 1] != C[i + j - 1])
IL[i, j] = IL[i - 1, j];
// Current character of C matches
// with current character of B, but
// doesn't match with current
// character if A
else if (A[i - 1] != C[i + j - 1] &&
B[j - 1] == C[i + j - 1])
IL[i, j] = IL[i, j - 1];
// Current character of C matches
// with that of both A and B
else if (A[i - 1] == C[i + j - 1] &&
B[j - 1] == C[i + j - 1])
IL[i, j] = (IL[i - 1, j] ||
IL[i, j - 1]);
}
}
return IL[M, N];
}
// Function to run test cases
static void test(string A, string B, string C)
{
if (isInterleaved(A, B, C))
Console.WriteLine(C + " is interleaved of " +
A + " and " + B);
else
Console.WriteLine(C + " is not interleaved of " +
A + " and " + B);
}
// Driver code
static void Main()
{
test("XXY", "XXZ", "XXZXXXY");
test("XY", "WZ", "WZXY");
test("XY", "X", "XXY");
test("YX", "X", "XXY");
test("XXY", "XXZ", "XXXXZY");
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// A Dynamic Programming based program
// to check whether a string C is
// an interleaving of two other
// strings A and B.
// The main function that
// returns true if C is
// an interleaving of A
// and B, otherwise false.
function isInterleaved(A, B, C)
{
// Find lengths of the two strings
let M = A.length, N = B.length;
// Let us create a 2D table
// to store solutions of
// subproblems. C[i][j] will
// be true if C[0..i+j-1]
// is an interleaving of
// A[0..i-1] and B[0..j-1].
// Initialize all values as false.
let IL = new Array(M + 1);
for(let i=0;i<M+1;i++){
IL[i] = new Array(N + 1).fill(0);
}
// C can be an interleaving of
// A and B only of the sum
// of lengths of A & B is equal
// to the length of C.
if ((M + N) != C.length)
return false;
// Process all characters of A and B
for (let i = 0; i <= M; ++i) {
for (let j = 0; j <= N; ++j) {
// two empty strings have an
// empty string as interleaving
if (i == 0 && j == 0)
IL[i][j] = true;
// A is empty
else if (i == 0) {
if (B[j - 1] == C[j - 1])
IL[i][j] = IL[i][j - 1];
}
// B is empty
else if (j == 0) {
if (A[i - 1] == C[i - 1])
IL[i][j] = IL[i - 1][j];
}
// Current character of C matches
// with current character of A,
// but doesn't match with current
// character of B
else if (
A[i - 1] == C[i + j - 1]
&& B[j - 1] != C[i + j - 1])
IL[i][j] = IL[i - 1][j];
// Current character of C matches
// with current character of B,
// but doesn't match with current
// character of A
else if (
A[i - 1] != C[i + j - 1]
&& B[j - 1] == C[i + j - 1])
IL[i][j] = IL[i][j - 1];
// Current character of C matches
// with that of both A and B
else if (
A[i - 1] == C[i + j - 1]
&& B[j - 1] == C[i + j - 1])
IL[i][j]
= (IL[i - 1][j]
|| IL[i][j - 1]);
}
}
return IL[M][N];
}
// A function to run test cases
function test(A, B, C)
{
if (isInterleaved(A, B, C))
document.write(C + " is interleaved of " + A + " and " + B,"</br>");
else
document.write(C + " is not interleaved of " + A + " and " + B,"</br>");
}
// Driver program to test above functions
test("XXY", "XXZ", "XXZXXXY");
test("XY", "WZ", "WZXY");
test("XY", "X", "XXY");
test("YX", "X", "XXY");
test("XXY", "XXZ", "XXXXZY");
// This code is contributed by shinjanpatra
</script>
C++
// A Memoization program
// to check whether a string C is
// an interleaving of two other
// strings A and B.
#include <iostream>
#include <string.h>
using namespace std;
// Declare n,m for storing the size of the strings.
int n, m;
// Declare dp array
int dp[101][101];
// declaration of dfs function.
bool dfs(int i, int j, string &A, string &B, string &C);
// The main function that
// returns true if C is
// an interleaving of A
// and B, otherwise false.
bool isInterleave(string A, string B, string C)
{
// Strong the length in n,m
n = A.length(), m = B.length();
// C can be an interleaving of
// A and B only of the sum
// of lengths of A & B is equal
// to the length of C.
if ((n + m) != C.length())
return 0;
// initializing dp array with -1
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
dp[i][j] = -1;
// calling and returning the answer
return dfs(0, 0, A, B, C);
}
// This function checks if there exist a valid path from 0,0 to n,m
bool dfs(int i, int j, string &A, string &B, string &C)
{
// If path has already been calculated from this index
// then return calculated value.
if (dp[i][j] != -1)
return dp[i][j];
// If we reach the destination return 1
if (i == n && j == m)
return 1;
// If C[i+j] matches with both A[i] and B[j]
// we explore both the paths
if (i < n && A[i] == C[i + j] && j < m && B[j] == C[i + j])
{
// go down and store the calculated value in x
// and go right and store the calculated value in y.
int x = dfs(i + 1, j, A, B, C), y = dfs(i, j + 1, A, B, C);
// return the best of both.
return dp[i][j] = x | y;
}
// If C[i+j] matches with A[i].
if (i < n && A[i] == C[i + j])
{
// go down
int x = dfs(i + 1, j, A, B, C);
// Return the calculated value.
return dp[i][j] = x;
}
// If C[i+j] matches with B[j].
if (j < m && B[j] == C[i + j])
{
int y = dfs(i, j + 1, A, B, C);
// Return the calculated value.
return dp[i][j] = y;
}
// if nothing matches we return 0
return dp[i][j] = 0;
}
// A function to run test cases
void test(string A, string B, string C)
{
if (isInterleave(A, B, C))
cout << C << " is interleaved of "
<< A << " and " << B << endl;
else
cout << C << " is not interleaved of "
<< A << " and " << B << endl;
}
// Driver program to test above functions
int main()
{
test("XXY", "XXZ", "XXZXXXY");
test("XY", "WZ", "WZXY");
test("XY", "X", "XXY");
test("YX", "X", "XXY");
test("XXY", "XXZ", "XXXXZY");
test("ACA", "DAS", "DAACSA");
return 0;
}
Java
// A Java Memoization program
// to check whether a string C is
// an interleaving of two other
// strings A and B.
import java.io.*;
class GFG {
// Declare n,m for storing the size of the strings.
static int n, m;
// Declare dp array
static int dp[][] = new int[100][100];
// declaration of dfs function.
// This function checks if there exist a valid path from
// 0,0 to n,m
public static int dfs(int i, int j, String A, String B,
String C)
{
// If path has already been calculated from this
// index then return calculated value.
if (dp[i][j] != -1)
return dp[i][j];
// If we reach the destination return 1
if (i == n && j == m)
return 1;
// If C[i+j] matches with both A[i] and B[j]
// we explore both the paths
if (i < n && A.charAt(i) == C.charAt(i + j) && j < m
&& B.charAt(j) == C.charAt(i + j)) {
// go down and store the calculated value in x
// and go right and store the calculated value
// in y.
int x = dfs(i + 1, j, A, B, C),
y = dfs(i, j + 1, A, B, C);
// return the best of both.
return dp[i][j] = x | y;
}
// If C[i+j] matches with A[i].
if (i < n && A.charAt(i) == C.charAt(i + j)) {
// go down
int x = dfs(i + 1, j, A, B, C);
// Return the calculated value.
return dp[i][j] = x;
}
// If C[i+j] matches with B[j].
if (j < m && B.charAt(j) == C.charAt(i + j)) {
int y = dfs(i, j + 1, A, B, C);
// Return the calculated value.
return dp[i][j] = y;
}
// if nothing matches we return 0
return dp[i][j] = 0;
}
// The main function that
// returns true if C is
// an interleaving of A
// and B, otherwise false.
public static int isInterleave(String A, String B,
String C)
{
// Strong the length in n,m
n = A.length();
m = B.length();
// C can be an interleaving of
// A and B only of the sum
// of lengths of A & B is equal
// to the length of C.
if ((n + m) != C.length())
return 0;
// initializing dp array with -1
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
dp[i][j] = -1;
// calling and returning the answer
return dfs(0, 0, A, B, C);
}
// A function to run test cases
public static void test(String A, String B, String C)
{
if (isInterleave(A, B, C) != 0)
System.out.println(C + " is interleaved of " + A
+ " and " + B);
else
System.out.println(C + " is not interleaved of "
+ A + " and " + B);
}
// Driver program to test above functions
public static void main(String[] args)
{
test("XXY", "XXZ", "XXZXXXY");
test("XY", "WZ", "WZXY");
test("XY", "X", "XXY");
test("YX", "X", "XXY");
test("XXY", "XXZ", "XXXXZY");
test("ACA", "DAS", "DAACSA");
}
}
// This code is contributed by Rohit Pradhan
Python3
# A Python Memoization program
# to check whether a string C is
# an interleaving of two other
# strings A and B.
# Declare dp array
dp = [[0]*101]*101
# This function checks if there exist a valid path from 0,0 to n,m
def dfs(i, j, A, B, C):
# If path has already been calculated from this index
# then return calculated value.
if(dp[i][j]!=-1):
return dp[i][j]
# If we reach the destination return 1
n,m=len(A),len(B)
if(i==n and j==m):
return 1
# If C[i+j] matches with both A[i] and B[j]
# we explore both the paths
if (i<n and A[i]==C[i + j] and j<m and B[j]==C[i + j]):
# go down and store the calculated value in x
# and go right and store the calculated value in y.
x = dfs(i + 1, j, A, B, C)
y = dfs(i, j + 1, A, B, C)
# return the best of both.
dp[i][j] = x|y
return dp[i][j]
# If C[i+j] matches with A[i].
if (i < n and A[i] == C[i + j]):
# go down
x = dfs(i + 1, j, A, B, C)
# Return the calculated value.
dp[i][j] = x
return dp[i][j]
# If C[i+j] matches with B[j].
if (j < m and B[j] == C[i + j]):
y = dfs(i, j + 1, A, B, C)
# Return the calculated value.
dp[i][j] = y
return dp[i][j]
# if nothing matches we return 0
dp[i][j] = 0
return dp[i][j]
# The main function that
# returns true if C is
# an interleaving of A
# and B, otherwise false.
def isInterleaved(A, B, C):
# Storing the length in n,m
n = len(A)
m = len(B)
# C can be an interleaving of
# A and B only of the sum
# of lengths of A & B is equal
# to the length of C.
if((n+m)!=len(C)):
return 0
# initializing dp array with -1
for i in range(n+1):
for j in range(m+1):
dp[i][j]=-1
# calling and returning the answer
return dfs(0,0,A,B,C)
# A function to run test cases
def test(A, B, C):
if (isInterleaved(A, B, C)):
print(C, "is interleaved of", A, "and", B)
else:
print(C, "is not interleaved of", A, "and", B)
# Driver Code
if __name__ == '__main__':
test("XXY", "XXZ", "XXZXXXY")
test("XY", "WZ", "WZXY")
test("XY", "X", "XXY")
test("YX", "X", "XXY")
test("XXY", "XXZ", "XXXXZY")
test("ACA", "DAS", "DAACSA")
# This code is contributed by Pushpesh Raj.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA