S - From S To T(有点难度的思维题(关于字符串配对字符))

S - From S To T(有点难度的思维题(关于字符串配对字符))
S - From S To T(有点难度的思维题(关于字符串配对字符))
S - From S To T(有点难度的思维题(关于字符串配对字符))
读这个题,首先应该知道题的意思就是从p串里面任意去字符插入s串里面(注意s串本身是不能删除的),然后最后判断s串能不能通过若干次变化和t串相等;
首先我应该知道,如果你要让两个串相等,那么两个串的字母个数和它们的下标位置必定相同,才能叫相等;所以:
1.先判断是不是s串中原本的字符位置在t串中满足(如果满足就用一个book[]数组标记满足了的字符);
2.判断剩下的t里面没有标记的字符在p中是否都有并且是否足够;
解决这两个问题就OK了;
AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 50050
int main(){
 string s,t,p;
   ll n,lens,lent,lenp,book[200];
   scanf("%lld",&n);
   while(n--){
   	   cin>>s>>t>>p;
   	   memset(book,0,sizeof(book));
   	    lens=s.length();lent=t.length();lenp=p.length();
   	   if(lens>lent){//长度更大就不行,因为s是不能删除的 
   	   	    puts("NO");continue;
		  }
   	   //比较s在t中的位置合不合法
   	   ll num=0,tt=-1;
		  for(int i=0;i<lens;i++){
		  	  for(int j=0;j<lent;j++){//保证先后顺序合法 
		  	  	    if(s[i]==t[j]&&j>tt){
		  	  	    	  num++;book[j]=1;tt=j;break;
						}
				}
		  }
		  if(num!=lens){
		    puts("NO");continue; 
	      }
		  //配对没有标记的t里面的字符和p中的相同字符的个数是否相同
		  for(int i=0;i<lent;i++){
		  	   if(!book[i]){
		  	   	  for(int j=0;j<p.length();j++){
					       if(t[i]==p[j]){
					       	  book[i]=1;
					       	  p.erase(j,1);
					       	  break;
						   }
					} 
				 }
		  }
		  ll flag=0;
		  for(int i=0;i<lent;i++){
		  	  if(!book[i]) {
				  puts("NO");flag=1;break;
				}
		  } 
		  
		  if(!flag) puts("YES");
   }
	return 0;
}
上一篇:388. Longest Absolute File Path


下一篇:01背包问题 JAVA