TopCoder problem "ListeningIn" used in SRM 254 (Division I Level One , Division II Level Two)



Problem Statement

    You are creating an online multiplayer cooperative game. Players on a team may chat with each other during the game, and you intend to take advantage of this when building the AI to handle opponents. Part of the AI includes determining whether a given phrase is part of a player's chat. Of course, many variations of a given phrase are possible, and you want to detect as many as you can. Shorthand is the most common example: instead of typing 'capture', a player might type 'cptr', or 'port to me' instead of 'teleport to me'. You will be provided with a String typed typed by a player and a phrase that you wish to check against. Return the characters removed from phrase to obtain typed in the order they appear in phrase or "UNMATCHED" if there is no way to obtain typed from phrase by simply removing characters. The constraints ensure that the return is unique (there is only one option for which String is returned).
 

Definition

    
Class:ListeningIn
Method:probableMatch
Parameters:String, String
Returns:String
Method signature:String probableMatch(String typed, String phrase)
(be sure your method is public)
    
 

Constraints

-typed and phrase will contain only lowercase letters ('a'-'z') and spaces
-typed and phrase will be between 1 and 50 characters long, inclusive.
-All valid groups of characters that could be removed to turn phrase into typed will give the same output.
 

Examples

0)
    
"cptr"
"capture"
Returns: "aue"
The example given in the problem statement.
1)
    
"port to me"
"teleport to me"
Returns: "tele"
The other example from the statement.
2)
    
"back  to base"
"back to base"
Returns: "UNMATCHED"
An extra space has been added; we do not account for additions, only deletions.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4670

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8006&pm=4670

Writer:

Enogipe

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Recursion