极客教程C++检查给定约束条件下一个字符串是否可以由另一个字符串形成
给定两个字符串S1和S2（所有字符均为小写）。任务是检查是否可以使用给定的约束条件从S1形成S2：
1. 如果S2中有两个字符’a’，则S1中也应该有两个字符’a’。
2. 如果S2中有任何一个字符不在S1中，则检查前两个ASCII字符是否在S1中。例如，如果’e’在S2中而不在S1中，则可以从S1中使用’c’和’d’来形成’e’。
注意： S1中的所有字符只能使用一次。
示例：
输入： S= abbat, W= cat
输出： YES
‘c’由’a’和’b’形成，’a’和’t’在S1中。
输入： S= abbt, W= cat
输出： NO
‘c’由’a’和’b’形成，但要形成S2中的下一个字符’a’，S1中没有更多未使用的字符’a’。
算法： 可以使用哈希表解决上述问题。在哈希表中存储S1中所有字符的计数。遍历该字符串，并检查S2中的字符是否在哈希表中，减少哈希表中特定字符的计数。如果哈希表中没有该字符，则检查前两个ASCII字符是否在哈希表中，然后减少哈希表中前两个ASCII字符的计数。如果所有字符都可以使用给定的约束条件从S1形成，则可以形成字符串S2，否则无法形成。
以下是上述方法的实现：
// CPP程序检查所给定的
//字符串是否可以从另一个字符串形成
#include <bits/stdc++.h>
using namespace std;
//检查S2是否可以由S1形成
bool check(string S1, string S2)
{
//字符串长度
int n1 = S1.size();
int n2 = S2.size();
//哈希表存储计数
unordered_map<int, int> mp;
//存储每个字符的计数
for (int i = 0; i < n1; i++) {
mp[S1[i]]++;
}
//遍历并检查每个字符
for (int i = 0; i < n2; i++) {
//如果s2的字符存在于s1中
if (mp[S2[i]]) {
mp[S2[i]]--;
}
//如果s2的字符不在S1中，则检查前两个ASCII字符
//是否在S1中
else if (mp[S2[i] - 1] && mp[S2[i] - 2]) {
mp[S2[i] - 1]--;
mp[S2[i] - 2]--;
}
else {
return false;
}
}
return true;
}
//司机代码
int main()
{
string S1 = "abbat";
string S2 = "cat";
//调用检查函数
if (check(S1, S2))
cout << "YES";
else
cout << "NO";
}
// JAVA程序，用于检查给定的字符串是否可以使用给定的约束条件从另一个字符串中形成
import java.util.*;
class GFG
{
// 检查S2是否可以由S1组成的函数
static boolean check(String S1, String S2)
{
// 字符串的长度
int n1 = S1.length();
int n2 = S2.length();
//哈希表来存储计数
HashMap<Integer,Integer> mp =
new HashMap<Integer,Integer>();
// 存储每个字符的数量
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);
}
}
// 遍历并检查每个字符
for (int i = 0; i < n2; i++)
{
// 如果S2的字符存在于S1中
if(mp.containsKey((int)S2.charAt(i)))
{
mp.put((int)S2.charAt(i),
mp.get((int)S2.charAt(i)) - 1);
}
// 如果S2的字符不在S1中，则检查前两个ASCII字符是否在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;
}
// 主要代码
public static void main(String[] args)
{
String S1 = "abbat";
String S2 = "cat";
// 调用检查函数
if (check(S1, S2))
System.out.print("YES");
else
System.out.print("NO");
}
}
// 本代码由PrinciRaj1992提供
# Python3程序，用于检查给定字符串是否可以使用给定约束条件从另一个字符串中形成
from collections import defaultdict
# 检查S2是否可以由S1组成的函数
def check(S1, S2):
# 字符串的长度
n1 = len(S1)
n2 = len(S2)
# 哈希表来存储计数
mp = defaultdict(lambda:0)
# 存储每个字符的数量
for i in range(0, n1):
mp[S1[i]] += 1
# 遍历并检查每个字符
for i in range(0, n2):
# 如果S2的字符存在于S1中
if mp[S2[i]]:
mp[S2[i]] -= 1
# 如果S2的字符不在S1中，则检查前两个ASCII字符是否在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
# 主要代码
if __name__ =="__main__":
S1 = "abbat"
S2 = "cat"
# 调用检查函数
if check(S1, S2):
print("YES")
else:
print("NO")
# 本代码由Rituraj Jain提供
// C#程序用于检查给定的
// 字符串是否可以使用给定约束条件从另一个字符串形成
using System;
using System.Collections.Generic;
class GFG
{
// 检查S2是否可以由S1形成的函数
static bool check(String S1, String S2)
{
// 字符串的长度
int n1 = S1.Length;
int n2 = S2.Length;
// 哈希表存储计数
Dictionary<int,int> mp =
new Dictionary<int,int>();
// 存储每个字符的计数
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);
}
}.
// 遍历并检查每个字符
for (int i = 0; i < n2; i++)
{
// 如果s2的字符存在于s1中
if(mp.ContainsKey((int)S2[i]))
{
mp[(int)S2[i]] = mp[(int)S2[i]] - 1;
}
// 如果s2的字符不在S1中，则检查前两个ASCII字符是否在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;
}
// 驱动代码
public static void Main(String[] args)
{
String S1 = "abbat";
String S2 = "cat";
// 调用函数检查
if (check(S1, S2))
Console.Write("YES");
else
Console.Write("NO");
}
}
// 该代码由PrinciRaj1992贡献
<script>
// JavaScript程序用于检查给定的
// 字符串是否可以使用给定约束条件从另一个字符串形成
// 检查S2是否可以由S1形成的函数
function check(S1, S2)
{
// 字符串的长度
var n1 = S1.length;
var n2 = S2.length;
// 哈希表存储计数
var mp = {};
// 存储每个字符的计数
for(var i = 0; i < n1; i++)
{
if (mp.hasOwnProperty(S1[i]))
{
mp[S1[i]] = mp[S1[i]] + 1;
}
else
{
mp[S1[i]] = 1;
}
}
// 遍历并检查每个字符
for(var i = 0; i < n2; i++)
{
// 如果s2的字符存在于s1中
if (mp.hasOwnProperty(S2[i]))
{
mp[S2[i]] = mp[S2[i]] - 1;
}
// 如果S2的字符不在S1中，则检查前两个ASCII
// 字符是否存在于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;
}
// 驱动代码
var S1 = "abbat";
var S2 = "cat";
// 调用函数检查
if (check(S1, S2))
document.write("YES");
else
document.write("NO");
// 该代码由rdtank贡献
</script>
输出：
YES