## Thursday, February 19, 2015

### DecipherabilityEasy

Problem:

 TopCoder Problem Statement - DecipherabilityEasy Single Round Match 649 Round 1 - Division II, Level One

Overview:

Determine if a string can be formed from another, by dropping a single character.

Java Source:
```01: public class DecipherabilityEasy {
02:
03:     public String check(String s, String t) {
04:
05:         // Make sure s has one character more than t
06:         if (s.length() != t.length() + 1) return "Impossible";
07:
08:         int sIdx = 0;
09:         int tIdx = 0;
10:
11:         // Walk through each letter in t.
12:         while (tIdx < t.length()) {
13:             if (s.charAt(sIdx) != t.charAt(tIdx)) {
14:
15:                 /*
16:                 * If the characters don't match up, it's ok the first time.
17:                 * Skip a letter in s and move on.  If it happens again,
18:                 * return Impossible.
19:                 */
20:                 if (sIdx == tIdx) {
21:                     sIdx++;
22:                 } else {
23:                     return "Impossible";
24:                 }
25:
26:             } else {
27:                 sIdx++;
28:                 tIdx++;
29:             }
30:         }
31:
32:         return "Possible";
33:
34:     }
35: }
```
Notes:

To solve this problem, we'll use two indexes sIdx and tIdx to walk through the Strings s and t. The indexes both start at position 0. So long as the characters are equal, the indexes increment together. If the character in s does not match the corresponding position in t, we'll advance sIdx - so long as sIdx and tIdx were previously equal. If the indexes were not equal, then we've found a second mismatch, so return "Impossible".

If we make it all the way to tIdx == t.length(), then return possible.

A check at the beginning of the method ensures that the length of s is exactly one character longer than t.