本文概述
- C ++
- C
- Java
- python
- C#
- 的PHP
解:
挑选一个C的每个字符, 并将其与A中的第一个字符匹配。如果不匹配, 则将其与B的第一个字符匹配。如果它甚至与B的第一个字符都不匹配, 则返回false。如果该字符与A的第一个字符匹配, 则从C的第二个字符, A的第二个字符和B的第一个字符重复上述过程。如果C的第一个字符与B的第一个字符匹配(并且不匹配A的第一个字符, 然后从C的第二个字符, A的第一个字符和B的第二个字符重复上述过程。如果C的所有字符都与A的字符或B的字符匹配, 并且C的长度为A和B的长度之和, 则C是A和B的交织。
C ++
// C++ program to check if given string is
// an interleaving of the other two strings
#include <
bits/stdc++.h>
using namespace std;
// Returns true if C is an interleaving of A and B, // otherwise returns false
bool isInterleaved ( char A[], char B[], char C[])
{
// Iterate through all characters of C.
while (*C != 0)
{
// Match first character of C with first character
// of A. If matches them move A to next
if (*A == *C)
A++;
// Else Match first character of C with first
// character of B. If matches them move B to next
else if (*B == *C)
B++;
// If doesn't match with either A or B, then return
// false
else
return false ;
// Move C to next for next iteration
C++;
} // If A or B still have some characters, then length of
// C is smaller than sum of lengths of A and B, so
// return false
if (*A || *B)
return false ;
return true ;
} // Driver program to test above functions
int main()
{
char A[] = "AB" ;
char B[] = "CD" ;
char C[] = "ACBG" ;
if (isInterleaved(A, B, C) == true )
cout <
<
C <
<
" is interleaved of " <
<
A <
<
" and " <
<
B;
else
cout <
<
C <
<
" is not interleaved of " <
<
A <
<
" and " <
<
B;
return 0;
} // This is code is contributed by rathbhupendra
C
// C program to check if given string is an interleaving
// of the other two strings
#include<
stdio.h>
// Returns true if C is an interleaving of A and B, // otherwise returns false
bool isInterleaved ( char *A, char *B, char *C)
{
// Iterate through all characters of C.
while (*C != 0)
{
// Match first character of C with first character
// of A. If matches them move A to next
if (*A == *C)
A++;
// Else Match first character of C with first
// character of B. If matches them move B to next
else if (*B == *C)
B++;
// If doesn't match with either A or B, then return
// false
else
return false ;
// Move C to next for next iteration
C++;
}// If A or B still have some characters, then length of
// Cis smaller than sum of lengths of A and B, so
// return false
if (*A || *B)
return false ;
return true ;
}// Driver program to test above functions
int main()
{
char *A = "AB" ;
char *B = "CD" ;
char *C = "ACBG" ;
if (isInterleaved(A, B, C) == true )
printf ( "%s is interleaved of %s and %s" , C, A, B);
else
printf ( "%s is not interleaved of %s and %s" , C, A, B);
return 0;
}// This code is contributed by Venkat
Java
// Java program to check if the given string is
// an interleaving of the other two strings
public class GfG{// Returns true if C is an interleaving
// of A and B, otherwise returns false
static boolean isInterleaved (String A, String B, String C)
{
int i = 0 , j = 0 , k = 0 ;
// Iterate through all characters of C.
while (k != C.length())
{
// Match first character of C with first character
// of A. If matches them move A to next
if (i<
A.length()&
&
A.charAt(i) == C.charAt(k))
i++;
// Else Match first character of C with first
// character of B. If matches them move B to next
else if (j<
B.length()&
&
B.charAt(j) == C.charAt(k))
j++;
// If doesn't match with either A or B, then return
// false
else
return false ;
// Move C to next for next iteration
k++;
} // If A or B still have some characters, // then length of C is smaller than sum
// of lengths of A and B, so return false
if (i <
A.length() || j <
B.length())
return false ;
return true ;
} public static void main(String []args){String A = "AB" ;
String B = "CD" ;
String C = "ACBG" ;
if (isInterleaved(A, B, C) == true )
System.out.printf( "%s is interleaved of %s and %s" , C, A, B);
else
System.out.printf( "%s is not interleaved of %s and %s" , C, A, B);
}
}// This code is contributed by Rituraj Jain
python
# Python program to check if given string is an interleaving of
# the other two strings# Returns true if C is an interleaving of A and B, otherwise
# returns false
def isInterleaved(A, B, C):# Utility variables
i = 0
j = 0
k = 0# Iterate through all characters of C.
while k ! = len (C) - 1 :# Match first character of C with first character of A, # If matches them move A to next
if i<
len (A) and A[i] = = C[k]:
i + = 1# Else Match first character of C with first character
# of B. If matches them move B to next
elif j<
len (B) and B[j] = = C[k]:
j + = 1# If doesn't match with either A or B, then return false
else :
return 0# Move C to next for next iteration
k + = 1# If A or B still have some characters, then length of C is
# smaller than sum of lengths of A and B, so return false
if A[i - 1 ] or B[j - 1 ]:
return 0return 1# Driver program to test the above function
A = "AB"
B = "CD"
C = "ACBG"
if isInterleaved(A, B, C) = = 1 :
print C + " is interleaved of " + A + " and " + B
else :
print C + " is not interleaved of " + A + " and " + B# This code is contributed by Bhavya Jain
C#
// C# program to check if the given string is
// an interleaving of the other two strings
using System;
class GfG
{// Returns true if C is an interleaving
// of A and B, otherwise returns false
static bool isInterleaved (String A, String B, String C)
{
int i = 0, j = 0, k = 0;
// Iterate through all characters of C.
while (k != C.Length - 1)
{
// Match first character of C with first character
// of A. If matches them move A to next
if (A[i] == C[k])
i++;
// Else Match first character of C with first
// character of B. If matches them move B to next
else if (B[j] == C[k])
j++;
// If doesn't match with either A or B, then return
// false
else
return false ;
// Move C to next for next iteration
k++;
} // If A or B still have some characters, // then length of C is smaller than sum
// of lengths of A and B, so return false
if (i <
A.Length || j <
B.Length)
return false ;
return true ;
} // Driver code
public static void Main(String []args)
{String A = "AB" ;
String B = "CD" ;
String C = "ACBG" ;
if (isInterleaved(A, B, C) == true )
Console.WriteLine( "{0} is interleaved of {1} and {2}" , C, A, B);
else
Console.WriteLine( "{0} is not interleaved of {1} and {2}" , C, A, B);
}
}// This code contributed by Rajput-Ji
的PHP
<
?php
// PHP program to check if given string
// is an interleaving of the other two strings// Returns true if C is an interleaving
// of A and B, otherwise returns false
function isInterleaved ( $A , $B , $C )
{
// Iterate through all characters of C.
while ( $C != 0)
{
// Match first character of C with
// first character of A. If matches
// them move A to next
if ( $A == $C )
$A ++;
// Else Match first character of C
// with first character of B. If
// matches them move B to next
else if ( $B == $C )
$B ++;
// If doesn't match with either
// A or B, then return false
else
return false;
// Move C to next for next iteration
$C ++;
}// If A or B still have some characters, // then length of C is smaller than sum
// of lengths of A and B, so return false
if ( $A || $B )
return false;
return true;
}// Driver Code
$A = "AB" ;
$B = "CD" ;
$C = "ACBG" ;
if (isInterleaved( $A , $B , $C ) == true)
echo $C . " is interleaved of " .
$A . " and " . $B ;
else
echo $C . " is not interleaved of " .
$A . " and " . $B ;
// This code is contributed by ita_c
?>
输出如下:
ACBG is not interleaved of AB and CD
时间复杂度:O(m + n)其中, m和n分别是字符串A和B的长度。
请注意, 如果A和B有一些共同的字符, 则上述方法无效。例如, 如果字符串A =" AAB", 字符串B =" AAC"和字符串C =" AACAAB", 则上述方法将返回false。我们已经讨论过这里是处理常见字符的扩展解决方案.
【对两个给定的字符串进行交织,没有共同的字符】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- 算法设计(如何反转给定大小的组中的数组())
- Node.js如何使用Buffer.writeUInt32LE()方法()
- 什么是标准访问列表(ACL)(详细指南)
- PHP convert_uudecode()函数用法详解
- 本文教你win7升级win10的办法
- 本文教你win7旗舰版忘记密码怎进入
- 暴风win7激活工具安装图文详细教程
- 最新推荐win7专业版与旗舰版的区别
- 本文教你怎样把win732位换成64位