Problem Statement
Guts is a slow loris who likes to play with strings.
String C is obtained by
shuffling strings A and B if we can create C by repeatedly taking either the first character of A or the first character of B. Formally, string C is obtained by shuffling strings A and B if length(C) = length(A) + length(B)
and there are sequences of integers X and Y such that:
length(X) = length(A) and length(Y) = length(B). For each valid i, X[i] < X[i+1]. For each valid i, Y[i] < Y[i+1]. For each valid i and j, X[i] != Y[j]. For each valid i, C[X[i]] = A[i]. For each valid i, C[Y[i]] = B[i].
You are given strings
S,
A, and
B. Strings
A and
B contain only letters, string
S can also contain multiple copies of the '?' (question mark) character. The '?' is a wildcard that represents any single letter. Guts wants to shuffle strings
A and
B in such a way that the resulting string matches
S.
Replace each '?' with a letter in such a way that the resulting string
S can be obtained by shuffling
A and
B. Return the resulting string
S. If there are multiple solutions, return the lexicographically smallest one. If there is no solution, return an empty string instead.
Definition
Class:
MergeStrings
Method:
getmin
Parameters:
string, string, string
Returns:
string
Method signature:
string getmin(string S, string A, string B)
(be sure your method is public)
Limits
Time limit (s):
2.000
Memory limit (MB):
256
Notes
-
Given two distinct strings X and Y such that length(X)=length(Y), the lexicographically smaller one is the one that has a character with a smaller ASCII value on the first position on which they differ.
Constraints
-
S will contain between 1 and 50 characters, inclusive.
-
The number of characters in
S will be same as the total number of characters of
A and
B.
-
Each character in
S will be an uppercase letter ('A'-'Z') or '?'.
-
Each character in
A and
B will be an uppercase letter ('A'-'Z').
Examples
0)
"??CC??"
"ABC"
"BCC"
Returns: "ABCCBC"
Out of all strings that can be obtained by shuffling "ABC" and "BCC", only two match "??CC??": the strings "ABCCBC" and "BACCBC". The string "ABCCBC" is the lexicographically smaller of the two.
1)
"WHAT?"
"THE"
"WA"
Returns: ""
None of the strings obtained by shuffling "THE" and "WA" matches "WHAT?".
2)
"PARROT"
"PARROT"
""
Returns: "PARROT"
One of
A and
B may sometimes be empty.
3)
"???????????"
"AZZAA"
"AZAZZA"
Returns: "AAZAZZAAZZA"
4)
"????K??????????????D???K???K????????K?????K???????"
"KKKKKDKKKDKKDDKDDDKDKK"
"KDKDDKKKDDKDDKKKDKDKKDDDDDDD"
Returns: "KDKDKDKKKDDKDDKKKDKDKKDKDDDKDDDKKDKKKDKKDDKDDDKDKK"
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
暴力。。。
class MergeStrings {
public:
string getmin(string, string, string);
};
int n,n1,n2;
#define pb push_back
string s,a,b;
string dp[88][88],m[66][66];
const string CANT="a",TRY="b";
int na,nb;
string dfs(int i,int j)
{
if(j==n)
return i==na? "" : CANT;
if(m[i][j]==TRY)
{
string t=CANT;
if(i
//Powered by [KawigiEdit] 2.0!
