Regexp metachars "*" and "*?" in the JAVA's replaceAll() method behave oddly [duplicate]

Question

Possible Duplicate:
String.replaceAll() anomaly with greedy quantifiers in regex
Strange behavior in regexes

While

"a".replaceAll("a", "b")
"a".replaceAll("a+", "b")
"a".replaceAll("a+?", "b")

all return b, why does

"a".replaceAll("a*", "b")

return bb and

"a".replaceAll("a*?", "b")

return bab?

Answer 1

"a".replaceAll("a*", "b")

First replaces a to b, then advances the pointer past the b. Then it matches the end of string, and replaces with b. Since it matched an empty string, it advances the pointer, falls out of the string, and finishes, resulting in bb.

"a".replaceAll("a*?", "b")

first matches the start of string and replaces with b. It doesn't match the a because ? in a*? means "non-greedy" (match as little as possible). Since it matched an empty string, it advances the pointer, skipping a. Then it matches the end of string, replaces with b and falls out of the string, resulting in bab. The end result is the same as if you did "a".replaceAll("", "b").

Answer 2

This happens because of zero-width matches.

"a".replaceAll("a*", "b")

Will match two times:

1. Try match at beginning of the string, greedy * consumes the a as a match.

2. Advance to the next position in the string (now at end of string), try match there, empty string matches.

   " a "
    \| \___ 2. match empty string
     \_____ 1. match "a"
   

"a".replaceAll("a*?", "b")

Will also match two times:

1. Try match at beginning of the string, non-greedy *? matches the empty string without consuming the a.

2. Advance to next position in the string (now at end of string), try match there, empty string matches.

   " a "
    \  \___ 2. match empty string
     \_____ 1. match empty string