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

2021年3月21日16:41:13 发表评论 841 次浏览

本文概述

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

// 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
     // 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 )
         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 0
  
     return 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
?>

输出如下：