TopCoder Problem Statement - DecipherabilityEasy |

Single Round Match 649 Round 1 - Division II, Level One |

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

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: }

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.

## No comments:

## Post a Comment