Рубрики

Проверьте, возможно ли преобразовать одну строку в другую

Даны две строки s1 и s2 (вызов букв в верхнем регистре). Проверьте, возможно ли преобразовать s1 в s2, выполнив следующие операции.

1. Make some lowercase letters uppercase.
2. Delete all the lowercase letters.

Примеры:

Input : s1 = daBcd s2 = ABC 
Output : yes
Explanation : daBcd -> dABCd -> ABC  
Convert a and b at index 1 and 3 to 
upper case, delete the rest those are 
lowercase. We get the string s2. 

Input : s1 = argaju    s2 = RAJ
Output : yes 
Explanation : argaju -> aRgAJu -> RAJ  
convert index 1, 3 and 4 to uppercase 
and then delete. All lowercase letters

Input : s1 = ABcd s2= BCD 
Output : NO

Подходить:
Пусть DP i, j будет 1, если возможно преобразовать первые i символов s1 в j символов s2, иначе DP i, j = 0. Тщательное наблюдение дает нам два условия для решения.

Первоначально DP 0, 0 = 1, если DP i, j = 1, то можно проверить следующие наборы, используя следующие условия.
1. Если s1 [i] в верхнем регистре равно s2 [j], то можно преобразовать i + 1 символов s1 в j + 1 символов s2, следовательно, DP i + 1, j + 1 = 1.

2. Если s1 [i] в нижнем регистре, то этот элемент можно удалить, и, следовательно, i + 1 символов можно преобразовать в j символов s2. Следовательно, DP i + 1, j = 1.

Если DP n, m = 1, то можно преобразовать s1 в s2, выполнив следующие условия.

Ниже приводится иллюстрация CPP вышеупомянутого подхода.

C ++

// программа cpp для проверки, может ли строка
// преобразовать в другую строку
// выполнение операций
#include <bits/stdc++.h>

using namespace std;

  
// функция для проверки, может ли быть строка
// преобразовать в другую строку
// выполнение следующих операций

bool check(string s1, string s2)

{

    // вычисляет длину

    int n = s1.length();

    int m = s2.length();

  

    bool dp[n + 1][m + 1];

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

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

            dp[i][j] = false;

        }

    }

    // пометить первую позицию как истинную

    dp[0][0] = true;

  

    // путешествия для всех DPi, j

    for (int i = 0; i < s1.length(); i++) {

        for (int j = 0; j <= s2.length(); j++) {

  

            // если возможно для преобразования я

            // символы от s1 до j символов

            // из s2

            if (dp[i][j]) {

  

                // if upper_case (s1 [i]) == s2 [j]

                // такой же

                if (j < s2.length() && 

                    (toupper(s1[i]) == s2[j]))

                    dp[i + 1][j + 1] = true;

  

                // если не верхний то удаление

                // возможно

                if (!isupper(s1[i]))

                    dp[i + 1][j] = true;

            }

        }

    }

  

    return (dp[n][m]);

}

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

int main()

{

    string s1 = "daBcd";

    string s2 = "ABC";

  

    if (check(s1, s2))

        cout << "YES";

    else

        cout << "NO";

  

    return 0;

}

Джава

// Java-программа для проверки, может ли строка
// преобразовать в другую строку
// выполнение операций

import java.io.*;

  

class GFG {

      

    // функция для проверки, может ли быть строка

    // преобразовать в другую строку

    // выполнение следующих операций

    static boolean check(String s1, String s2)

    {

        // вычисляет длину

        int n = s1.length();

        int m = s2.length();

      

        boolean dp[][]=new boolean[n + 1][m + 1];

        for (int i = 0; i <= n; i++) 

        {

            for (int j = 0; j <= m; j++)

            {

                dp[i][j] = false;

            }

        }

        // пометить первую позицию как истинную

        dp[0][0] = true;

      

        // путешествия для всех DPi, j

        for (int i = 0; i < s1.length(); i++)

        {

            for (int j = 0; j <= s2.length(); j++)

            {

      

                // если возможно для преобразования я

                // символы от s1 до j символов

                // из s2

                if (dp[i][j]) {

      

                    // if upper_case (s1 [i]) == s2 [j]

                    // такой же

                    if (j < s2.length() && 

                        (Character.toUpperCase(s1.charAt(i)) == s2.charAt(j)))

                        dp[i + 1][j + 1] = true;

      

                    // если не верхний то удаление

                    // возможно

                    if (!Character.isUpperCase(s1.charAt(i)))

                        dp[i + 1][j] = true;

                }

            }

        }

      

        return (dp[n][m]);

    }

      

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

    public static void main(String args[])

    {

        String s1 = "daBcd";

        String s2 = "ABC";

      

        if (check(s1, s2))

            System.out.println("YES");

        else

            System.out.println("NO");

      

    }

}

  
// Этот код предоставлен Никитой Тивари.

python3

# Python3 программа для проверки, может ли строка
# быть преобразованным в другую строку
# выполнение операций

  

  
# функция для проверки, может ли быть строка
# преобразован в другую строку
# выполнение следующих операций

def check(s1,s2):

      

    # рассчитывает длину

    n = len(s1)

    m = len(s2)

    dp=([[False for i in range(m+1)]

       for i in range(n+1)])

      

    # пометить первую позицию как истинную

    dp[0][0] = True

      

    # путешественник для всех DPi, j

    for i in range(len(s1)):

        for j in range(len(s2)+1):

              

            # если возможно для преобразования я

            # символов от s1 до j символов

            # из s2

            if (dp[i][j]):

                  

                # if upper_case (s1 [i]) == s2 [j]

                # такой же

                if ((j < len(s2) and 

                   (s1[i].upper()== s2[j]))):

                    dp[i + 1][j + 1] = True

                      

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

                # возможно

                if (s1[i].isupper()==False):

                    dp[i + 1][j] = True

    return (dp[n][m])

  
# код водителя

if __name__=='__main__':

  

    s1 = "daBcd"

    s2 = "ABC"

    if (check(s1, s2)):

        print("YES")

    else:

        print("NO")

  
# этот код предоставлен
# sahilshelangia

C #

// C # программа для проверки, может ли строка
// преобразовать в другую строку
// выполнение операций

using System;

  

class GFG 

{

  
// функция для проверки, может ли быть строка
// преобразовать в другую строку
// выполнение следующих операций

static bool check(string s1, string s2)

{

    // вычисляет длину

    int n = s1.Length;

    int m = s2.Length;

  

    bool[,] dp = new bool[n + 1, m + 1];

    for (int i = 0; i <= n; i++) 

    {

        for (int j = 0; j <= m; j++)

        {

            dp[i, j] = false;

        }

    }

      

    // пометить первую позицию как истинную

    dp[0, 0] = true;

  

    // путешествия для всех DPi, j

    for (int i = 0; i < s1.Length; i++)

    {

        for (int j = 0; j <= s2.Length; j++)

        {

  

            // если возможно для преобразования я

            // символы от s1 до j символов

            // из s2

            if (dp[i, j]) 

            {

  

                // if upper_case (s1 [i]) == s2 [j]

                // такой же

                if (j < s2.Length && 

                    (Char.ToUpper(s1[i]) == s2[j]))

                    dp[i + 1, j + 1] = true;

  

                // если не верхний то удаление

                // возможно

                if (!Char.IsUpper(s1[i]))

                    dp[i + 1, j] = true;

            }

        }

    }

  

    return (dp[n, m]);

}

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

public static void Main()

{

    string s1 = "daBcd";

    string s2 = "ABC";

  

    if (check(s1, s2))

        Console.Write("YES");

    else

        Console.Write("NO");

}
}

  
// Этот код добавлен
// ChitraNayal


Выход:

YES

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

Проверьте, возможно ли преобразовать одну строку в другую

0.00 (0%) 0 votes