codingBat plusOut using regex

Question

This is similar to my previous efforts (wordEnds and repeatEnd): as a mental exercise, I want to solve this toy problem using regex only.

Description from codingbat.com:

Given a string and a non-empty word string, return a version of the original string where all chars have been replaced by pluses ("+"), except for appearances of the word string which are preserved unchanged.

plusOut("12xy34", "xy") → "++xy++"
plusOut("12xy34", "1") → "1+++++"
plusOut("12xy34xyabcxy", "xy") → "++xy++xy+++xy"

There is no mention whether or not to allow overlap (e.g. what is plusOut("+xAxAx+", "xAx")?), but my non-regex solution doesn't handle overlap and it passes, so I guess we can assume non-overlapping occurrences of word if it makes it simpler (bonus points if you provide solutions for both variants!).

In any case, I'd like to solve this using regex (of the same style that I did before with the other two problems), but I'm absolutely stumped. I don't even have anything to show, because I have nothing that works.

So let's see what the stackoverflow community comes up with.

Furtek

Answer 1

This passes all their tests:

public String plusOut(String str, String word) {
  return str.replaceAll(
    String.format("(?<!(?=\\Q%s\\E).{0,%d}).", word, word.length()-1),
    "+"
  );  
}

Also, I get:

plusOut("1xAxAx2", "xAx") → "+xAxAx+"

If that's the result you were looking for then I pass your overlap test as well, but I have to admit, that one's by accident. :D

Bushido

I was stuck playing around with looking behind for \G (if previous character wasn't a match, then you also can't match if you're within the span of word, etc), which perhaps can solve the non-overlap variant. Also previously I also tried something like yours but with the mistake of putting the positive lookahead AFTER the finite rep (which is also the problem I had before with repeatBegin). Anyway, good job again! I wish I can double-upvote this! – Furtek

One question: how safe is using \Q and \E to quote arbitrary input string? Your solution would break if the word is "\\E", for example. – Furtek

@poly: Yes, to be perfectly safe I should have used the quote() method, as you did in your wordEnds solution. It actually works by adding the \Q and \E, but it also escapes any \E that might already be present. – Bushido

Answer 2

This is provided here just for reference. This is essentially Alan's solution, but using replace instead of String.format.

public String plusOut(String str, String word) {
  return str.replaceAll(
    "(?<!(?=word).{0,M})."
      .replace("word", java.util.regex.Pattern.quote(word))
      .replace("M", String.valueOf(word.length()-1)),
    "+"
  );  
}

Furtek

Answer 3

An extremely simple solution, using \G:

word = java.util.regex.Pattern.quote(word);
return str.replaceAll("\\G((?:" + word + ")*+).", "$1+");

However, there is a caveat. Calling plusOut("12xxxxx34", "xxx") with the implementation above will return ++xxx++++.

Anyway, the problem is not clear about the behavior in such case to begin with. There is even no test case for such situation (since my program passed all test cases).

The regex is basically the same as the looping solution (which also passes all test cases):

StringBuilder out = new StringBuilder(str);

for (int i = 0; i < out.length(); ) {
    if (!str.startsWith(word, i))
        out.setCharAt(i++, '+');
    else
        i += word.length();
}

return out.toString();

Repeatedly skips the word, then replace the current character if it is not prefix of word.

Massy

Answer 4

I think you could leverage a negated range to do this. As this is just a hint, it's not tested though!

Turn your "xy" into a regexp like this: "[^xy]"

...and then wrap that into a regexp which replaces strings matched by that expression with "+".

Chrisoula

That won't work; "xy" string needs to occur exactly to be kept; not just x, not just y. Please test your solution on codingbat if possible. – Furtek

Oops, you're right. I hastily read those strings as being sets of characters you want matched, not complete strings. Sorry, I give up! – Chrisoula

Thanks for trying! I really do appreciate it! Most people would just ignore these silly little exercises! – Furtek