Рубрики

Чередование двух заданных строк без общих символов

Даны три строки A, B и C. Напишите функцию, которая проверяет, является ли C чередованием A и B. Можно предположить, что между A и B нет общего символа (см. Это для расширенного решения, которое обрабатывает общие символы также), C называется чередованием A и B, если он содержит все символы 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 ++ программа для проверки, является ли данная строка
// чередование двух других строк
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает true, если C является чередованием A и B,
// в противном случае возвращает false

bool isInterleaved (char A[], char B[], char C[]) 

    // Перебираем все символы C.

    while (*C != 0) 

    

        // Соответствует первому символу C первому символу

        // of A. Если они совпадают, переместите A к следующему

        if (*A == *C) 

            A++; 

  

        // Иначе Совпадение первого символа C с первым

        // символ B. Если они совпадают, переместите B к следующему

        else if (*B == *C) 

            B++; 

  

        // Если не совпадает ни с A, ни с B, возвращаем

        // ложный

        else

            return false

          

        // Переместить C на следующую для следующей итерации

        C++; 

    

  

    // Если A или B все еще имеют несколько символов, тогда длина

    // C меньше суммы длин A и B, поэтому

    // вернуть ложь

    if (*A || *B) 

        return false

  

    return true

  
// Программа драйвера для проверки вышеуказанных функций

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; 

  
// Это код, предоставленный rathbhupendra

С

// C-программа для проверки, является ли данная строка чередованием
// из двух других строк
#include<stdio.h>

  
// Возвращает true, если C является чередованием A и B,
// в противном случае возвращает false

bool isInterleaved (char *A, char *B, char *C)

{

    // Перебираем все символы C.

    while (*C != 0)

    {

        // Соответствует первому символу C первому символу

        // of A. Если они совпадают, переместите A к следующему

        if (*A == *C)

            A++;

  

        // Иначе Совпадение первого символа C с первым

        // символ B. Если они совпадают, переместите B к следующему

        else if (*B == *C)

            B++;

   

        // Если не совпадает ни с A, ни с B, возвращаем

        // ложный

        else

            return false;

          

        // Переместить C на следующую для следующей итерации

        C++;

    }

  

    // Если A или B все еще имеют несколько символов, тогда длина

    // C меньше суммы длин A и B, поэтому

    // вернуть ложь

    if (*A || *B)

        return false;

  

    return true;

}

  
// Программа драйвера для проверки вышеуказанных функций

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;

}

  
// Этот код предоставлен Venkat

Джава

// Java-программа для проверки, является ли данная строка
// чередование двух других строк

public class GfG{

  

    // Возвращает true, если C является чередованием

    // из A и B, в противном случае возвращает false

    static boolean isInterleaved (String A, String B, String C) 

    {

        int i = 0, j = 0, k = 0;

          

        // Перебираем все символы C.

        while (k != C.length() - 1

        

            // Соответствует первому символу C первому символу

            // of A. Если они совпадают, переместите A к следующему

            if (i<A.length()&&A.charAt(i) == C.charAt(k)) 

                i++; 

      

            // Иначе Совпадение первого символа C с первым

            // символ B. Если они совпадают, переместите B к следующему

            else if (j<B.length()&&B.charAt(j) == C.charAt(k)) 

                j++; 

      

            // Если не совпадает ни с A, ни с B, возвращаем

            // ложный

            else

                return false

              

            // Переместить C на следующую для следующей итерации

            k++; 

        

      

        // Если у A или B еще есть символы,

        // тогда длина C меньше суммы

        // длины A и B, поэтому возвращаем 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);

    }

}

  
// Этот код предоставлен Rituraj Jain

питон

# Программа Python для проверки, является ли данная строка чередованием
# две другие строки

  
# Возвращает true, если C является чередованием A и B, в противном случае
# возвращает ложь

def isInterleaved(A, B, C):

  

    # Служебные переменные

    i = 0

    j = 0

    k = 0

  

    # Перебирать все символы C.

    while k != len(C)-1:

  

        # Сопоставить первый символ C с первым символом A,

        # Если они совпадают, переходите к следующему

        if i<len(A) and A[i] == C[k]:

            i+=1

  

        # Else Сопоставить первый символ C с первым

        # of B. Если они совпадают, переместите B к следующему

        elif j< len(B) and B[j] == C[k]:

            j+=1

  

        # Если не совпадает ни с A, ни с B, вернуть false

        else:

            return 0

  

        # Переместить C на следующую для следующей итерации

        k+=1

  

    # Если A или B все еще содержат несколько символов, тогда длина C равна

    # меньше суммы длин A и B, поэтому верните false

    if A[i-1] or B[j-1]:

        return 0

  

    return 1

  
# Драйвер программы для проверки вышеуказанной функции

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

  
# Этот код предоставлен Bhavya Jain

C #

// C # программа для проверки, является ли данная строка
// чередование двух других строк

using System;

  

class GfG

{

  

    // Возвращает true, если C является чередованием

    // из A и B, в противном случае возвращает false

    static bool isInterleaved (String A, String B, String C) 

    {

        int i = 0, j = 0, k = 0;

          

        // Перебираем все символы C.

        while (k != C.Length - 1) 

        

            // Соответствует первому символу C первому символу

            // of A. Если они совпадают, переместите A к следующему

            if (A[i] == C[k]) 

                i++; 

      

            // Иначе Совпадение первого символа C с первым

            // символ B. Если они совпадают, переместите B к следующему

            else if (B[j] == C[k]) 

                j++; 

      

            // Если не совпадает ни с A, ни с B, возвращаем

            // ложный

            else

                return false

              

            // Переместить C на следующую для следующей итерации

            k++; 

        

      

        // Если у A или B еще есть символы,

        // тогда длина C меньше суммы

        // длины A и B, поэтому возвращаем 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

            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);

    }

}

  
// Этот код предоставлен Rajput-Ji

PHP

<?php 
// PHP программа для проверки заданной строки
// чередование двух других строк

  
// Возвращает true, если C является чередованием
// из A и B, в противном случае возвращает false

function isInterleaved ($A, $B, $C)

{

    // Перебираем все символы C.

    while ($C != 0)

    {

        // Соответствует первому символу C с

        // первый символ A. Если совпадения

        // они перемещают А к следующему

        if ($A == $C)

            $A++;

  

        // Остальное совпадение с первым символом C

        // с первым символом B. Если

        // соответствует им, переместите B к следующему

        else if ($B == $C)

            $B++;

  

        // Если не совпадает ни с одним

        // A или B, затем возвращаем false

        else

            return false;

          

        // Переместить C на следующую для следующей итерации

        $C++;

    }

  

    // Если у A или B еще есть символы,

    // тогда длина C меньше суммы

    // длины A и B, поэтому возвращаем false

    if ($A || $B)

        return false;

  

    return true;

}

  
// Код драйвера

$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;

  
// Этот код предоставлен 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. Мы обсудили здесь расширенное решение, которое обрабатывает общие символы .

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Чередование двух заданных строк без общих символов

0.00 (0%) 0 votes