Monday, December 29, 2014

DoubleLetter

Problem:

TopCoder Problem Statement - DoubleLetter
Single Round Match 630 Round 1 - Division II, Level One

Overview:

Remove double letters from the left side of a String until no more double letters exist.

Java Source:
01: public class DoubleLetter {
02: 
03:     public String ableToSolve(String S) {
04: 
05:         // A StringBuilder will be much more efficient for deleting characters.
06:         StringBuilder sb = new StringBuilder(S);
07: 
08:         boolean changed = true;
09: 
10:         while (changed) {
11:             changed = false;
12: 
13:             for (int i = 0; i < sb.length() - 1; i++) {
14:                 if (sb.charAt(i) == sb.charAt(i + 1)) {
15:                     sb.deleteCharAt(i);
16:                     sb.deleteCharAt(i);
17:                     changed = true;
18: 
19:                     // Start over from the left of the string.
20:                     break;
21:                 }
22:             }
23:         }
24: 
25:         return (sb.length() == 0) ? "Possible" : "Impossible";
26:     }
27: }
Notes:

First, I create a StringBuilder object out of the given String. This will make deleting characters from the string more efficient. Every time a String is modified in Java, a new object is created. On the other hand, StringBuilder is mutable.

I used the boolean variable changed to note when any characters have been deleted. If we pass through the entire string with no changes, then we're done. Note that I call sb.deleteCharAt(i) twice. The first deletes the first characters, and causes all subsequent characters to shift one place to the left. The second call deletes the second of the double characters.

Upon exiting the while loop, simply check the size of the remaining string, and return Possible or Impossible accordingly.

No comments:

Post a Comment