给定两个字符串S1和S2（所有字符均为小写）。任务是检查是否可以使用给定的约束条件从S1形成S2： 1.S1中有S2的字符如果S2中有两个“a”，那么S1也应该有两个“a”。 2.如果S1中没有S2的任何字符，请检查S1中是否有前两个ASCII字符。e、 例如，如果“e”在S2中，而不是在S1中，那么可以从S1中使用“c”和“d”来表示“e”。 注： S1中的所有字符只能使用一次。
null
例如：
输入： S=阿巴特，W=猫 输出： 对 “c”由“a”和“b”组成，“a”和“t”出现在S1中。
输入： S=缩写，W=猫 输出： 不 “c”是由“a”和“b”组成的，但构成下一个字符 S2中的“a”在S1中不再剩下未使用的“a”。
方法： 上述问题可以通过使用哈希来解决。S1中所有字符的计数存储在哈希表中。遍历字符串，检查S2中的字符是否在哈希表中，减少哈希表中该特定字符的计数。如果该字符不在哈希表中，请检查前两个ASCII字符是否在哈希表中，然后减少哈希表中前两个ASCII字符的计数。如果所有字符都可以使用给定的约束从S1形成，那么字符串S2可以从S1形成，否则无法形成。
以下是上述方法的实施情况：
C++
// CPP program to Check if a given // string can be formed from another // string using given constraints #include <bits/stdc++.h> using namespace std; // Function to check if S2 can be formed of S1 bool check(string S1, string S2) { // length of strings int n1 = S1.size(); int n2 = S2.size(); // hash-table to store count unordered_map< int , int > mp; // store count of each character for ( int i = 0; i < n1; i++) { mp[S1[i]]++; } // traverse and check for every character for ( int i = 0; i < n2; i++) { // if the character of s2 is present in s1 if (mp[S2[i]]) { mp[S2[i]]--; } // if the character of s2 is not present in // S1, then check if previous two ASCII characters // are present in S1 else if (mp[S2[i] - 1] && mp[S2[i] - 2]) { mp[S2[i] - 1]--; mp[S2[i] - 2]--; } else { return false ; } } return true ; } // Driver Code int main() { string S1 = "abbat" ; string S2 = "cat" ; // Calling function to check if (check(S1, S2)) cout << "YES" ; else cout << "NO" ; } |
JAVA
// JAVA program to Check if a given // String can be formed from another // String using given constraints import java.util.*; class GFG { // Function to check if S2 can be formed of S1 static boolean check(String S1, String S2) { // length of Strings int n1 = S1.length(); int n2 = S2.length(); // hash-table to store count HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // store count of each character for ( int i = 0 ; i < n1; i++) { if (mp.containsKey(( int )S1.charAt(i))) { mp.put(( int )S1.charAt(i), mp.get(( int )S1.charAt(i)) + 1 ); } else { mp.put(( int )S1.charAt(i), 1 ); } } // traverse and check for every character for ( int i = 0 ; i < n2; i++) { // if the character of s2 is present in s1 if (mp.containsKey(( int )S2.charAt(i))) { mp.put(( int )S2.charAt(i), mp.get(( int )S2.charAt(i)) - 1 ); } // if the character of s2 is not present in // S1, then check if previous two ASCII characters // are present in S1 else if (mp.containsKey(S2.charAt(i)- 1 ) && mp.containsKey(S2.charAt(i)- 2 )) { mp.put((S2.charAt(i) - 1 ), mp.get(S2.charAt(i) - 1 ) - 1 ); mp.put((S2.charAt(i) - 2 ), mp.get(S2.charAt(i) - 2 ) - 1 ); } else { return false ; } } return true ; } // Driver Code public static void main(String[] args) { String S1 = "abbat" ; String S2 = "cat" ; // Calling function to check if (check(S1, S2)) System.out.print( "YES" ); else System.out.print( "NO" ); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to Check if a given string # can be formed from another string using # given constraints from collections import defaultdict # Function to check if S2 can # be formed of S1 def check(S1, S2): # length of strings n1 = len (S1) n2 = len (S2) # hash-table to store count mp = defaultdict( lambda : 0 ) # store count of each character for i in range ( 0 , n1): mp[S1[i]] + = 1 # traverse and check for every character for i in range ( 0 , n2): # if the character of s2 is # present in s1 if mp[S2[i]]: mp[S2[i]] - = 1 # if the character of s2 is not present # in S1, then check if previous two ASCII # characters are present in S1 elif (mp[ chr ( ord (S2[i]) - 1 )] and mp[ chr ( ord (S2[i]) - 2 )]): mp[ chr ( ord (S2[i]) - 1 )] - = 1 mp[ chr ( ord (S2[i]) - 2 )] - = 1 else : return False return True # Driver Code if __name__ = = "__main__" : S1 = "abbat" S2 = "cat" # Calling function to check if check(S1, S2): print ( "YES" ) else : print ( "NO" ) # This code is contributed by Rituraj Jain |
C#
// C# program to Check if a given // String can be formed from another // String using given constraints using System; using System.Collections.Generic; class GFG { // Function to check if S2 can be formed of S1 static bool check(String S1, String S2) { // length of Strings int n1 = S1.Length; int n2 = S2.Length; // hash-table to store count Dictionary< int , int > mp = new Dictionary< int , int >(); // store count of each character for ( int i = 0; i < n1; i++) { if (mp.ContainsKey(( int )S1[i])) { mp[( int )S1[i]] = mp[( int )S1[i]] + 1; } else { mp.Add(( int )S1[i], 1); } } // traverse and check for every character for ( int i = 0; i < n2; i++) { // if the character of s2 is present in s1 if (mp.ContainsKey(( int )S2[i])) { mp[( int )S2[i]] = mp[( int )S2[i]] - 1; } // if the character of s2 is not present in // S1, then check if previous two ASCII characters // are present in S1 else if (mp.ContainsKey(S2[i] - 1) && mp.ContainsKey(S2[i] - 2)) { mp[S2[i] - 1] = mp[S2[i] - 1] - 1; mp[S2[i] - 2] = mp[S2[i] - 2] - 1; } else { return false ; } } return true ; } // Driver Code public static void Main(String[] args) { String S1 = "abbat" ; String S2 = "cat" ; // Calling function to check if (check(S1, S2)) Console.Write( "YES" ); else Console.Write( "NO" ); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript program to Check if a given // String can be formed from another // String using given constraints // Function to check if S2 can be formed of S1 function check(S1, S2) { // Length of Strings var n1 = S1.length; var n2 = S2.length; // hash-table to store count var mp = {}; // Store count of each character for ( var i = 0; i < n1; i++) { if (mp.hasOwnProperty(S1[i])) { mp[S1[i]] = mp[S1[i]] + 1; } else { mp[S1[i]] = 1; } } // Traverse and check for every character for ( var i = 0; i < n2; i++) { // If the character of s2 is present in s1 if (mp.hasOwnProperty(S2[i])) { mp[S2[i]] = mp[S2[i]] - 1; } // If the character of s2 is not present // in S1, then check if previous two ASCII // characters are present in S1 else if (mp.hasOwnProperty( String.fromCharCode(S2[i].charCodeAt(0) - 1)) && mp.hasOwnProperty( String.fromCharCode(S2[i].charCodeAt(0) - 2))) { mp[String.fromCharCode( S2[i].charCodeAt(0) - 1)] = mp[String.fromCharCode( S2[i].charCodeAt(0) - 1)] - 1; mp[String.fromCharCode( S2[i].charCodeAt(0) - 2)] = mp[String.fromCharCode( S2[i].charCodeAt(0) - 2)] - 1; } else { return false ; } } return true ; } // Driver Code var S1 = "abbat" ; var S2 = "cat" ; // Calling function to check if (check(S1, S2)) document.write( "YES" ); else document.write( "NO" ); // This code is contributed by rdtank </script> |
输出：
YES
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
