Thursday, April 8, 2010

CodingBat string manipulation problems - Part 2

Continuing on with the series, this part shows basic uses of lookarounds and the split counting idiom.

Lookarounds

frontAgain: Given a string of any length, return true if the first 2 chars in the string also appear at the end of the string (allowing overlap).
public boolean frontAgain(String str) {
  return str.matches("(?=(..)).*\\1");
}

An alternative solution to doubleChar (see also: Part 1). Instead of matching every character and replacing it with its double, match empty strings and replace it with the character following it.
public String doubleChar(String str) {
  return str.replaceAll("(?=(.))", "$1");
}

Lookarounds and anchors

stringX: Given a string, return a version where all the "x" have been removed. Except an "x" at the very start or end should not be removed.
public String stringX(String str) {
  return str.replaceAll("(?<!^)x(?!$)", "");
}
withoutX2: Given a string, if one or both of the first 2 chars is 'x', return the string without those 'x' chars, and otherwise return the string unchanged.
public String withoutX2(String str) {
  return str.replaceAll("(?<=^.?)x", "");
}

stringBits: Given a string, return a string made of every other char starting with the first.
public String stringBits(String str) {
  return str.replaceAll("(?<=\\G.).", "");
}
altPairs: Given a string, return a string made of the chars at indexes 0,1, 4,5, 8,9 ...
public String altPairs(String str) {
  return str.replaceAll("(..)..?", "$1");
}
These two problems are essentially cousins. I choose to demonstrate the two possible approaches to solving them; they are each adaptable to both problems:
  • Match exactly those characters that needs to be removed, using lookbehind to find the \G end of last match boundary anchor.
  • Match both "keep" and "delete" parts, and replace only with the "keep" part.

Occurrence counting

countCode: Return the number of times that the string "code" appears anywhere in the given string, except we'll accept any letter for the 'd'.
public int countCode(String str) {
  return str.split("co.e", -1).length - 1;
}
Time/space inefficiency aside, this (haystack.split(needle, -1).length - 1) counting idiom is actually really handy!
countTriple: We'll say that a "triple" in a string is a char appearing three times in a row. Return the number of triples in the given string. The triples may overlap.
public int countTriple(String str) {
  return str.split("(.)(?=\\1\\1)", -1).length - 1;
}

No comments:

Post a Comment