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

01.01.2020Строки

Для двух строк 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>

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