对两个给定的字符串进行交织，没有共同的字符

本文概述

C ++
C
Java
python
C#
的PHP

给定三个字符串A, B和C。编写一个函数, 检查C是否是A和B的交织。可以假定A和B之间没有公共字符(请参阅这个对于也处理常见字符的扩展解决方案), 如果C包含A和B的所有字符并且保留了各个字符串中所有字符的顺序, 则称C交织了A和B。看到以前的帖子举些例子。
解：
挑选一个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 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# 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。我们已经讨论过这里是处理常见字符的扩展解决方案.
【对两个给定的字符串进行交织，没有共同的字符】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。