Рубрики

Распечатать все чередования данных двух строк

Для двух строк str1 и str2 напишите функцию, которая печатает все чередования данных двух строк. Вы можете предположить, что все символы в обеих строках разные

Пример:

Input: str1 = "AB",  str2 = "CD"
Output:
    ABCD
    ACBD
    ACDB
    CABD
    CADB
    CDAB

Input: str1 = "AB",  str2 = "C"
Output:
    ABC
    ACB
    CAB

Чередованная строка данных двух строк сохраняет порядок символов в отдельных строках. Например, во всех перемежениях первого примера «A» предшествует «B», а «C» предшествует «D».

Пусть длина str1 равна m, а длина str2 равна n. Предположим, что все символы в str1 и str2 различны. Пусть count (m, n) будет количеством всех чередующихся строк в таких строках. Значение count (m, n) можно записать следующим образом.

     count(m, n) = count(m-1, n) + count(m, n-1)
     count(1, 0) = 1 and count(0, 1) = 1

Чтобы распечатать все чередования, мы можем сначала исправить первый символ str1 [0..m-1] в выходной строке и рекурсивно вызвать str1 [ 1 ..m-1] и str2 [0..n-1]. И тогда мы можем исправить первый символ str2 [0..n-1] и рекурсивно вызвать str1 [0..m-1] и str2 [ 1 ..n-1]. Спасибо akash01 за предоставление следующей реализации C.

C ++

// C ++ программа для печати всех чередований заданных двух строк
#include <bits/stdc++.h>

using namespace std; 

  
// Основная функция, которая рекурсивно печатает все чередования.
// Переменная iStr используется для хранения всех чередований (или
// выводим строки) по очереди.
// я используется для передачи следующего доступного места в iStr

void printIlsRecur (char *str1, char *str2, char *iStr, int m, 

                    int n, int i) 

    // Базовый случай: если все символы str1 и str2 были

    // включаем в выходную строку, затем печатаем выходную строку

    if (m == 0 && n == 0) 

        cout << iStr << endl ; 

  

    // Если для включения осталось несколько символов str1, то

    // включить первый символ из оставшихся символов

    // и вернемся к отдыху

    if (m != 0) 

    

        iStr[i] = str1[0]; 

        printIlsRecur (str1 + 1, str2, iStr, m - 1, n, i + 1); 

    

  

    // Если для включения осталось несколько символов str2, то

    // включить первый символ из оставшихся символов

    // и вернемся к отдыху

    if (n != 0) 

    

        iStr[i] = str2[0]; 

        printIlsRecur(str1, str2 + 1, iStr, m, n - 1, i + 1); 

    

  
// выделяет память для выходной строки и использует printIlsRecur ()
// для печати всех чередований

void printIls (char *str1, char *str2, int m, int n) 

    // выделяем память для выходной строки

    char *iStr= new char[((m + n + 1)*sizeof(char))]; 

      

    // Установить терминатор для выходной строки

    iStr[m + n] = '\0'

      

    // распечатать все чередования, используя printIlsRecur ()

    printIlsRecur (str1, str2, iStr, m, n, 0); 

      

    // свободная память, чтобы избежать утечки памяти

    free(iStr); 

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

int main() 

    char str1[] = "AB"

    char str2[] = "CD"

    printIls (str1, str2, strlen(str1), strlen(str2)); 

    return 0; 

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

С

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

  
// Основная функция, которая рекурсивно печатает все чередования.
// Переменная iStr используется для хранения всех чередований (или
// выводим строки) по очереди.
// я используется для передачи следующего доступного места в iStr

void printIlsRecur (char *str1, char *str2, char *iStr, int m, 

                    int n, int i)

{

    // Базовый случай: если все символы str1 и str2 были

    // включаем в выходную строку, затем печатаем выходную строку

    if (m==0 && n==0)

        printf("%s\n", iStr) ;

  

    // Если для включения осталось несколько символов str1, то

    // включить первый символ из оставшихся символов

    // и вернемся к отдыху

    if (m != 0)

    {

        iStr[i] = str1[0];

        printIlsRecur (str1 + 1, str2, iStr, m-1, n, i+1);

    }

  

    // Если для включения осталось несколько символов str2, то

    // включить первый символ из оставшихся символов

    // и вернемся к отдыху

    if (n != 0)

    {

        iStr[i] = str2[0];

        printIlsRecur(str1, str2+1, iStr, m, n-1, i+1);

    }

}

  
// выделяет память для выходной строки и использует printIlsRecur ()
// для печати всех чередований

void printIls (char *str1, char *str2, int m, int n)

{

   // выделяем память для выходной строки

   char *iStr= (char*)malloc((m+n+1)*sizeof(char));

  

   // Установить терминатор для выходной строки

   iStr[m+n] = '\0';

  

   // распечатать все чередования, используя printIlsRecur ()

   printIlsRecur (str1, str2, iStr, m, n, 0);

  

   // свободная память, чтобы избежать утечки памяти

   free(iStr); 

}

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

int main()

{

    char str1[] = "AB";

    char str2[] = "CD";

    printIls (str1, str2, strlen(str1), strlen(str2));

    return 0;

}

питон

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

  
# Вспомогательная функция

def toString(List):

    return "".join(List)

  
# Основная функция, которая рекурсивно печатает все чередования.
# Переменная iStr используется для хранения всех чередований (или вывода
# строки) по одному.
# i используется для прохождения следующего доступного места в iStr

def printIlsRecur(str1, str2, iStr, m, n, i):

  

    # Базовый случай: если все символы str1 и str2 были

    # включается в выходную строку, затем печатает выходную строку

    if m==0 and n==0:

        print toString(iStr)

  

    # Если некоторые символы из str1 оставлены для включения, то

    # включить первый символ из оставшихся символов

    # и повторить для отдыха

    if m != 0:

        iStr[i] = str1[0]

        printIlsRecur(str1[1:], str2, iStr, m-1, n, i+1)

  

    # Если некоторые символы из str2 оставлены для включения, то

    # включить первый символ из оставшихся символов

    # и повторить для отдыха

    if n != 0:

        iStr[i] = str2[0]

        printIlsRecur(str1, str2[1:], iStr, m, n-1, i+1)

  
# Распределяет память для выходной строки и использует printIlsRecur ()
# для печати всех чередований

def printIls(str1, str2, m, n):

    iStr = [''] * (m+n)

  

    # печатать все чередования, используя printIlsRecur ()

    printIlsRecur(str1, str2, iStr, m, n, 0)

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

str1 = "AB"

str2 = "CD"

printIls(str1, str2, len(str1), len(str2))

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


Выход:

ABCD
ACBD
ACDB
CABD
CADB
CDAB

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

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

Распечатать все чередования данных двух строк

0.00 (0%) 0 votes