原题

C - Airport Code

原题

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 300 points

Problem Statement
A string T of length 3 consisting of uppercase English letters is an airport code for a string S of lowercase English letters if and only if T can be derived from S by one of the following methods:

Take a subsequence of length 3 from S (not necessarily contiguous) and convert it to uppercase letters to form T.
Take a subsequence of length 2 from S (not necessarily contiguous), convert it to uppercase letters, and append X to the end to form T.
Given strings S and T, determine if T is an airport code for S.

Constraints
S is a string of lowercase English letters with a length between 3 and 10 
5
 , inclusive.
T is a string of uppercase English letters with a length of 3.

代码

思路dfs

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>

using namespace std;

string s, t;
const int convert = int('a' - 'A');
int n;

void dfs1(string curr, int k, int len)
{
	if (len == 3)
	{
		if (curr == t) 
		{
			cout << "Yes" << endl;
			exit(0); 
		}
		return ;
	}
	if (k == n) return ;
	
	dfs1(curr + char(s[k] - char(convert)), k + 1, len + 1);
	dfs1(curr, k + 1, len);
}

void dfs2(string curr, int k, int len)
{
	if (len == 2)
	{
		curr += 'X';
		if (curr == t) 
		{
			cout << "Yes" << endl;
			exit(0); 
		}
		curr.pop_back();
		return ;
	}
	if (k == n) return ;
	
	dfs2(curr + char(s[k] - (char)convert), k + 1, len + 1);
	dfs2(curr, k + 1, len);
}

int main()
{
	cin >> s >> t;
	
	n = s.length();
	dfs1("", 0, 0);
	dfs2("", 0, 0);
	
	cout << "No" << endl;
	
	return 0;
}