Рубрики

Найти, если строка чередуется с двумя другими строками | DP-33

Даны три строки A, B и C. Напишите функцию, которая проверяет, является ли C чередованием A и B. C называется чередованием A и B, если он содержит все символы A и B и порядок всех символов в отдельных строках сохраняется.

Мы обсудили простое решение этой проблемы здесь . Простое решение не работает, если строки A и B имеют несколько общих символов. Например, A = «XXY», строка B = «XXZ» и строка C = «XXZXXXY». Для обработки всех случаев необходимо рассмотреть две возможности.

a) Если первый символ C совпадает с первым символом A, мы передвигаемся на один символ вперед в A и C и рекурсивно проверяем.

б) Если первый символ C совпадает с первым символом B, мы передвигаемся на один символ вперед в B и C и рекурсивно проверяем.

Если какой-либо из двух приведенных выше случаев имеет значение true, мы возвращаем true, иначе false. Ниже приводится простая рекурсивная реализация этого подхода (спасибо Фредерику за предложение)

// Простая рекурсивная функция для проверки, является ли C чередованием A и B

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

{

    // Базовый случай: если все строки пусты

    if (!(*A || *B || *C))

        return true;

  

    // Если C пуст и любая из двух строк не пуста

    if (*C == '\0')

        return false;

  

    // Если любая из вышеупомянутых двух возможностей верна,

    // затем возвращаем true, иначе false

    return ((*C == *A) && isInterleaved(A + 1, B, C + 1))

           || ((*C == *B) && isInterleaved(A, B + 1, C + 1));

}

Динамическое программирование
Наихудшая временная сложность рекурсивного решения — O (2 n ). Вышеуказанное рекурсивное решение, безусловно, имеет много перекрывающихся подзадач. Например, если мы рассмотрим A = «XXX», B = «XXX» и C = «XXXXXX» и нарисуем дерево рекурсии, будет много перекрывающихся подзадач.
Поэтому, как и другие типичные проблемы динамического программирования , мы можем решить ее, создав таблицу и сохранив результаты подзадач в восходящем порядке. Спасибо Абхинаву Рамане за то, что он предложил этот метод и реализацию.

C ++

// Программа на основе динамического программирования для проверки, является ли строка C
// чередование двух других строк A и B.
#include <iostream>
#include <string.h>

using namespace std;

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

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

{

    // Находим длины двух строк

    int M = strlen(A), N = strlen(B);

  

    // Давайте создадим 2D-таблицу для хранения решений

    // подзадачи. C [i] [j] будет истинным, если C [0..i + j-1]

    // является чередованием A [0..i-1] и B [0..j-1].

    bool IL[M + 1][N + 1];

  

    memset(IL, 0, sizeof(IL)); // Инициализировать все значения как ложные.

  

    // C может быть чередованием A и B только суммы

    // длины A & B равны длине C.

    if ((M + N) != strlen(C))

        return false;

  

    // Обрабатываем все символы A и B

    for (int i = 0; i <= M; ++i) {

        for (int j = 0; j <= N; ++j) {

            // две пустые строки имеют пустую строку

            // как чередование

            if (i == 0 && j == 0)

                IL[i][j] = true;

  

            // А пусто

            else if (i == 0) {

                if (B[j - 1] == C[j - 1])

                    IL[i][j] = IL[i][j - 1];

            }

  

            // B пусто

            else if (j == 0) {

                if (A[i - 1] == C[i - 1])

                    IL[i][j] = IL[i - 1][j];

            }

  

            // Текущий символ C совпадает с текущим символом A,

            // но не совпадает с текущим символом B

            else if (A[i - 1] == C[i + j - 1] && B[j - 1] != C[i + j - 1])

                IL[i][j] = IL[i - 1][j];

  

            // Текущий символ C совпадает с текущим символом B,

            // но не совпадает с текущим символом A

            else if (A[i - 1] != C[i + j - 1] && B[j - 1] == C[i + j - 1])

                IL[i][j] = IL[i][j - 1];

  

            // Текущий символ C совпадает с символом A и B

            else if (A[i - 1] == C[i + j - 1] && B[j - 1] == C[i + j - 1])

                IL[i][j] = (IL[i - 1][j] || IL[i][j - 1]);

        }

    }

  

    return IL[M][N];

}

  
// Функция для запуска тестовых случаев

void test(char* A, char* B, char* C)

{

    if (isInterleaved(A, B, C))

        cout << C << " is interleaved of " << A << " and " << B << endl;

    else

        cout << C << " is not interleaved of " << A << " and " << B << endl;

}

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

int main()

{

    test("XXY", "XXZ", "XXZXXXY");

    test("XY", "WZ", "WZXY");

    test("XY", "X", "XXY");

    test("YX", "X", "XXY");

    test("XXY", "XXZ", "XXXXZY");

    return 0;

}

python3

# Программа Python3 на основе динамического программирования
# проверить, является ли строка C чередованием
# двух других строк A и B.

  
# Основная функция, которая возвращает true, если C
# чередование A и B, иначе ложь.

def isInterleaved(A, B, C): 

  

    # Найти длину двух строк

    M = len(A)

    N = len(B) 

  

    # Давайте создадим 2D-таблицу для хранения решений

    # подзадачи. C [i] [j] будет истинным, если C [0..i + j-1]

    # - это чередование A [0..i-1] и B [0..j-1].

    # Инициализировать все значения как ложные.

    IL = [[False] * (N + 1) for i in range(M + 1)] 

  

    # C может быть чередованием A и B только суммы

    Количество длин A & B равно длине C.

    if ((M + N) != len(C)): 

        return False

  

    # Обработка всех символов A и B

    for i in range(0, M + 1): 

        for j in range(0, N + 1):

              

            # две пустые строки имеют пустую строку

            # как чередование

            if (i == 0 and j == 0): 

                IL[i][j] = True

  

            # A пуст

            elif (i == 0): 

                if (B[j - 1] == C[j - 1]): 

                    IL[i][j] = IL[i][j - 1

              

            # B пуст

            elif (j == 0): 

                if (A[i - 1] == C[i - 1]): 

                    IL[i][j] = IL[i - 1][j] 

              

            # Текущий символ C совпадает с

            # текущий символ A, но не совпадает

            # с текущим символом B

            elif (A[i - 1] == C[i + j - 1] and

                  B[j - 1] != C[i + j - 1]): 

                IL[i][j] = IL[i - 1][j] 

  

            # Текущий символ C совпадает с

            # текущий символ B, но не совпадает

            # с текущим символом A

            elif (A[i - 1] != C[i + j - 1] and 

                  B[j - 1] == C[i + j - 1]): 

                IL[i][j] = IL[i][j - 1

  

            # Текущий символ C совпадает с

            # это как А, так и В

            elif (A[i - 1] == C[i + j - 1] and 

                  B[j - 1] == C[i + j - 1]): 

                IL[i][j] = (IL[i - 1][j] or IL[i][j - 1]) 

          

    return IL[M][N] 

  
# Функция для запуска тестовых случаев

def test(A, B, C): 

  

    if (isInterleaved(A, B, C)): 

        print(C, "is interleaved of", A, "and", B) 

    else:

        print(C, "is not interleaved of", A, "and", B)

  
Код водителя

if __name__ == '__main__'

    test("XXY", "XXZ", "XXZXXXY"

    test("XY", "WZ", "WZXY"

    test("XY", "X", "XXY"

    test("YX", "X", "XXY"

    test("XXY", "XXZ", "XXXXZY"

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


Выход:

XXZXXXY is not interleaved of XXY and XXZ
WZXY is interleaved of XY and WZ
XXY is interleaved of XY and X
XXY is not interleaved of YX and X
XXXXZY is interleaved of XXY and XXZ

Смотрите это для более тестовых случаев.

Сложность времени: O (MN)
Вспомогательное пространство: O (MN)

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

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

Найти, если строка чередуется с двумя другими строками | DP-33

0.00 (0%) 0 votes