检查是否可以将一个字符串转换为另一个字符串-yiteyi-C++库

给定两个字符串s1和s2（大写呼号）。检查是否可以通过执行以下操作将s1转换为s2。

null

1.使一些小写字母大写。 2.删除所有小写字母。

例如：

Input : s1 = daBcd s2 = ABC Output : yesExplanation : 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 = RAJOutput : yes Explanation : argaju -> aRgAJu -> RAJ  convert index 1, 3 and 4 to uppercase and then delete. All lowercase lettersInput : s1 = ABcd s2= BCD Output : NO

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法： 让DP _{i、 j} 如果可以将s1的前i个字符转换为s2的j个字符，则为1，否则为DP _{i、 j} 近距离观察给了我们两个需要处理的条件。最初的DP _{0, 0} =1，如果DP _{i、 j} =1则可以使用以下条件检查下一组。 1. 如果大写的s1[i]等于s2[j]，则可以将s1的i+1个字符转换为s2的j+1个字符，因此 数据处理 _i+1，j+1 =1. 2. 如果s1[i]是小写，则可以删除该元素，因此i+1字符可以转换为s2的j字符。因此 数据处理 _i+1，j =1. 如果 数据处理 _{n、 m} =1, 然后可以通过以下方式将s1转换为s2 条件

下面是CPP对上述方法的说明。

C++

                         // cpp program to check if a string can                       
                         // be converted to another string by                       
                         // performing operations                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to check if a string can be                       
                         // converted to  another string by                       
                         // performing following operations                       
                         bool                                     check(string s1, string s2)                       
                         {                       
                                                 // calculates length                       
                                                 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                                     ;                       
                                                 }                       
                                                 }                       
                                                 // mark 1st position as true                       
                                                 dp[0][0] =                                     true                                     ;                       
           
                                                 // traverse for all DPi, j                       
                                                 for                                     (                                     int                                     i = 0; i < s1.length(); i++) {                       
                                                 for                                     (                                     int                                     j = 0; j <= s2.length(); j++) {                       
           
                                                 // if possible for to convert i                       
                                                 // characters of s1 to j characters                       
                                                 // of s2                       
                                                 if                                     (dp[i][j]) {                       
           
                                                 // if upper_case(s1[i])==s2[j]                       
                                                 // is same                       
                                                 if                                     (j < s2.length() &&                       
                                                 (                                     toupper                                     (s1[i]) == s2[j]))                       
                                                 dp[i + 1][j + 1] =                                     true                                     ;                       
           
                                                 // if not upper then deletion is                       
                                                 // possible                       
                                                 if                                     (!                                     isupper                                     (s1[i]))                       
                                                 dp[i + 1][j] =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 return                                     (dp[n][m]);                       
                         }                       
           
                         // driver code                       
                         int                                     main()                       
                         {                       
                                                 string s1 =                                     "daBcd"                                     ;                       
                                                 string s2 =                                     "ABC"                                     ;                       
           
                                                 if                                     (check(s1, s2))                       
                                                 cout <<                                     "YES"                                     ;                       
                                                 else                       
                                                 cout <<                                     "NO"                                     ;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to check if a string can                       
                         // be converted to another string by                       
                         // performing operations                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                                   
                                                 // function to check if a string can be                       
                                                 // converted to another string by                       
                                                 // performing following operations                       
                                                 static                                     boolean                                     check(String s1, String s2)                       
                                                 {                       
                                                 // calculates length                       
                                                 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                                     ;                       
                                                 }                       
                                                 }                       
                                                 // mark 1st position as true                       
                                                 dp[                                     0                                     ][                                     0                                     ] =                                     true                                     ;                       
                                   
                                                 // traverse for all DPi, j                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < s1.length(); i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j <= s2.length(); j++)                       
                                                 {                       
                                   
                                                 // if possible for to convert i                       
                                                 // characters of s1 to j characters                       
                                                 // of s2                       
                                                 if                                     (dp[i][j]) {                       
                                   
                                                 // if upper_case(s1[i])==s2[j]                       
                                                 // is same                       
                                                 if                                     (j < s2.length() &&                       
                                                 (Character.toUpperCase(s1.charAt(i)) == s2.charAt(j)))                       
                                                 dp[i +                                     1                                     ][j +                                     1                                     ] =                                     true                                     ;                       
                                   
                                                 // if not upper then deletion is                       
                                                 // possible                       
                                                 if                                     (!Character.isUpperCase(s1.charAt(i)))                       
                                                 dp[i +                                     1                                     ][j] =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     (dp[n][m]);                       
                                                 }                       
                                   
                                                 // driver code                       
                                                 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"                                     );                       
                                   
                                                 }                       
                         }                       
           
                         // This code is contributed by Nikita Tiwari.                       

Python3

                         # Python3 program to check if a string can                       
                         # be converted to another string by                       
                         # performing operations                       
           
           
                         # function to check if a string can be                       
                         # converted to another string by                       
                         # performing following operations                       
                         def                                     check(s1,s2):                       
                                   
                                                 # calculates length                       
                                                 n                                     =                                     len                                     (s1)                       
                                                 m                                     =                                     len                                     (s2)                       
                                                 dp                                     =                                     ([[                                     False                                     for                                     i                                     in                                     range                                     (m                                     +                                     1                                     )]                       
                                                 for                                     i                                     in                                     range                                     (n                                     +                                     1                                     )])                       
                                   
                                                 # mark 1st position as true                       
                                                 dp[                                     0                                     ][                                     0                                     ]                                     =                                     True                       
                                   
                                                 # traverse for all DPi, j                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (s1)):                       
                                                 for                                     j                                     in                                     range                                     (                                     len                                     (s2)                                     +                                     1                                     ):                       
                                   
                                                 # if possible for to convert i                       
                                                 # characters of s1 to j characters                       
                                                 # of s2                       
                                                 if                                     (dp[i][j]):                       
                                   
                                                 # if upper_case(s1[i])==s2[j]                       
                                                 # is same                       
                                                 if                                     ((j <                                     len                                     (s2)                                     and                       
                                                 (s1[i].upper()                                     =                                     =                                     s2[j]))):                       
                                                 dp[i                                     +                                     1                                     ][j                                     +                                     1                                     ]                                     =                                     True                       
                                   
                                                 # if not upper then deletion is                       
                                                 # possible                       
                                                 if                                     (s1[i].isupper()                                     =                                     =                                     False                                     ):                       
                                                 dp[i                                     +                                     1                                     ][j]                                     =                                     True                       
                                                 return                                     (dp[n][m])                       
           
                         # driver code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
           
                                                 s1                                     =                                     "daBcd"                       
                                                 s2                                     =                                     "ABC"                       
                                                 if                                     (check(s1, s2)):                       
                                                 print                                     (                                     "YES"                                     )                       
                                                 else                                     :                       
                                                 print                                     (                                     "NO"                                     )                       
           
                         # this code is contributed by                       
                         # sahilshelangia                       

C#

                         // C# program to check if a string can                       
                         // be converted to another string by                       
                         // performing operations                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                         // function to check if a string can be                       
                         // converted to another string by                       
                         // performing following operations                       
                         static                                     bool                                     check(                                     string                                     s1,                                     string                                     s2)                       
                         {                       
                                                 // calculates length                       
                                                 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                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 // mark 1st position as true                       
                                                 dp[0, 0] =                                     true                                     ;                       
           
                                                 // traverse for all DPi, j                       
                                                 for                                     (                                     int                                     i = 0; i < s1.Length; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = 0; j <= s2.Length; j++)                       
                                                 {                       
           
                                                 // if possible for to convert i                       
                                                 // characters of s1 to j characters                       
                                                 // of s2                       
                                                 if                                     (dp[i, j])                       
                                                 {                       
           
                                                 // if upper_case(s1[i])==s2[j]                       
                                                 // is same                       
                                                 if                                     (j < s2.Length &&                       
                                                 (Char.ToUpper(s1[i]) == s2[j]))                       
                                                 dp[i + 1, j + 1] =                                     true                                     ;                       
           
                                                 // if not upper then deletion is                       
                                                 // possible                       
                                                 if                                     (!Char.IsUpper(s1[i]))                       
                                                 dp[i + 1, j] =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 return                                     (dp[n, m]);                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 string                                     s1 =                                     "daBcd"                                     ;                       
                                                 string                                     s2 =                                     "ABC"                                     ;                       
           
                                                 if                                     (check(s1, s2))                       
                                                 Console.Write(                                     "YES"                                     );                       
                                                 else                       
                                                 Console.Write(                                     "NO"                                     );                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by ChitraNayal                       

Javascript

                         <script>                       
                         // Javascript program to check if a string can                       
                         // be converted to another string by                       
                         // performing operations                       
                                   
                                   
                                                 // function to check if a string can be                       
                                                 // converted to another string by                       
                                                 // performing following operations                       
                                                 function                                     check(s1,s2)                       
                                                 {                       
                                                 // calculates length                       
                                                 let n = s1.length;                       
                                                 let m = s2.length;                       
                                   
                                                 let dp=                                     new                                     Array(n + 1);                       
                                                 for                                     (let i = 0; i <= n; i++)                       
                                                 {                       
                                                 dp[i]=                                     new                                     Array(m+1);                       
                                                 for                                     (let j = 0; j <= m; j++)                       
                                                 {                       
                                                 dp[i][j] =                                     false                                     ;                       
                                                 }                       
                                                 }                       
                                                 // mark 1st position as true                       
                                                 dp[0][0] =                                     true                                     ;                       
                                   
                                                 // traverse for all DPi, j                       
                                                 for                                     (let i = 0; i < s1.length; i++)                       
                                                 {                       
                                                 for                                     (let j = 0; j <= s2.length; j++)                       
                                                 {                       
                                   
                                   
                                                 // if possible for to convert i                       
                                                 // characters of s1 to j characters                       
                                                 // of s2                       
                                                 if                                     (dp[i][j]) {                       
                                   
                                                 // if upper_case(s1[i])==s2[j]                       
                                                 // is same                       
                                                 if                                     (j < s2.length &&                       
                                                 (s1[i].toUpperCase() == s2[j]))                       
                                                 dp[i + 1][j + 1] =                                     true                                     ;                       
                                   
                                                 // if not upper then deletion is                       
                                                 // possible                       
                                   
                                                 if                                     (!(s1[i] == s1[i].toUpperCase()))                       
                                                 dp[i + 1][j] =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     (dp[n][m]);                       
                                                 }                       
                                   
                                                 // driver code                       
                                                 let s1 =                                     "daBcd"                                     ;                       
                                                 let s2 =                                     "ABC"                                     ;                       
                                                 if                                     (check(s1, s2))                       
                                                 document.write(                                     "YES"                                     );                       
                                                 else                       
                                                 document.write(                                     "NO"                                     );                       
           
                                   
                                   
                                                 // This code is contributed by avanitrachhadiya2155                       
                         </script>                       

输出：

YES

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章