劳动最光荣！Double Letter Problem from TopCoder

包子IT面试培训 助你拿到理想的offer!

这是TopCoder上面一道比较简单的250分的题目，非常适合作为面试的第一道热身题目，考察了面试者对于基本的数据结构是否有所了解，如果简单暴力模拟的话，就不是很好。

话不多说，先看一下题目。

Problem Statement

   

You are given a String S. You can modify this string by repeating the following process:

Find the leftmost occurrence of two consecutive letters in S that are the same.

If you found a pair of identical letters in the first step, delete those two letters from S.

For example, if S="aabccb", you can proceed as follows:

Find and erase "aa", producing the string "bccb".

Find and erase "cc", producing the string "bb".

Find and erase "bb", producing the empty string.

For S="axxyybac" you can do at most two steps, erasing "xx" first and "yy" next. Once you obtain the string "abac", you are done. Note that you cannot erase the two "a"s because they are not consecutive. You want to change S into an empty string by repeating the operation described above. Return "Possible" if you can do that, and "Impossible" otherwise.

Definition

   

Class:

DoubleLetter

Method:

ableToSolve

Parameters:

String

Returns:

String

Method signature:

String ableToSolve(String S)

(be sure your method is public)

Limits

   

Time limit (s):

2.000

Memory limit (MB):

256

Constraints

-

S will contain between 1 and 50 characters.

-

Each character in S will be a lowercase English letter ('a'-'z').

Examples

0)

   

"aabccb"

Returns: "Possible"

1)

   

"aabccbb"

Returns: "Impossible"

The process will terminate with a single 'b'.

2)

   

"abcddcba"

Returns: "Possible"

"abcddcba" -> "abccba" -> "abba" -> "aa" -> "".

3)

   

"abab"

Returns: "Impossible"

No two successive letters are the same, so we can't do any operation.

4)

   

"aaaaaaaaaa"

Returns: "Possible"

5)

   

"aababbabbaba"

Returns: "Impossible"

6)

   

"zzxzxxzxxzzx"

Returns: "Possible"

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.

就像我们说的，如果面试者可以活用Stack，题目就变得非常容易，比简单的暴力模拟好很多，所以大家在面试的时候要因题而异，找准应该使用的数据结构，就会事半功倍。

代码如下