Nitori and Stack-Tech

第一行输入一个正整数n，表示n个零件。
第二行输入一个长度为n，由不同小写字母组成的字符串s，表示初始从左到右排列的n种零件。
第三行输入一个长度为n，由不同小写字母组成的字符串t，表示Nitori希望得到的排列。

数据规范：
* $1 \le n \le 26$ .
* 所有字符串保证只含有小写字母。

C(clang11) 解法, 执行用时: 7ms, 内存消耗: 376K, 提交时间: 2020-11-18 20:05:41

#include<stdio.h>
int main(void)
{
	char str1[27];char str2[27];
	char fa[27];
	int a;int n;int i=0;int ii=0;
	scanf("%d",&n);
	scanf("%s",&str1);
	scanf("%s",&str2); 
	for(a=0;a<n;a++)
	{
		fa[i]=str1[a];i++;
		while(fa[i-1]==str2[ii]&&i>0)
		{
			ii++;i--;
		}
	}
	if(ii==n)printf("Yes");
	else printf("No");
}

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 468K, 提交时间: 2020-06-14 12:21:35

#include<bits/stdc++.h>
using namespace std;
int n;
string s, t;
stack<char>st;
int main()
{
	cin >> n >> s >> t;
	for(int i = 0, j = 0; i < n; i++)
	{
		st.push(s[i]);
		for(; !st.empty() && st.top() == t[j]; j++, st.pop());
	}
	puts(st.empty() ? "Yes" : "No");
}

Python3(3.5.2) 解法, 执行用时: 21ms, 内存消耗: 3552K, 提交时间: 2020-06-15 08:48:31

n=int(input())
a=input()
b=input()
a1=[]
i=0
t=0
while i<n:
    a1.append(a[i])
    if a1[-1]==b[t]:
        t+=1
        a1.pop()
    while len(a1) and a1[-1]==b[t]:
        t+=1
        a1.pop()
    i+=1
if t==n:
    print("Yes")
else:
    print("No")

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 488K, 提交时间: 2020-06-18 00:03:48

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int i,j=0,t=0,n;
	char R[30],T[30],S[30];
	scanf("%d%s%s",&n,R,T);
	for(i=0;i<n;i++)
	{
		S[++t]=R[i];
		while(t&&T[j]==S[t])t--,j++;
	}
	if(!t)printf("Yes\n");
	else printf("No\n");
}

详情