Use regex to replace sequences in a string with modified characters

Question

I am trying to solve a codingbat problem using regular expressions whether it works on the website or not.

So far, I have the following code which does not add a * between the two consecutive equal characters. Instead, it just bulldozes over them and replaces them with a set string.

public String pairStar(String str) {
    Pattern pattern = Pattern.compile("([a-z])\\1", Pattern.CASE_INSENSITIVE);
    Matcher matcher = pattern.matcher(str);
    if(matcher.find())
    matcher.replaceAll(str);//this is where I don't know what to do
    return str;
}

I want to know how I could keep using regex and replace the whole string. If needed, I think a recursive system could help.

do i need one if it is just finding instances where it is 2 consecutive equal characters? — Wijagels
– Wijagels, Commented Dec 6, 2012 at 1:05
You need to add the '*' when you find the two equal characters. — Edward Falk
– Edward Falk, Commented Dec 6, 2012 at 1:17
FWIW, back-references are expensive. I just used a StringBuilder and scanned though the input. Oh, BTW, the codingbat problem didn't say anything about being case-insensitive. — Edward Falk
– Edward Falk, Commented Dec 6, 2012 at 1:18

Bohemian · Accepted Answer · 2012-12-06 01:42:32Z

2

This works:

while(str.matches(".*(.)\\1.*")) {
    str = str.replaceAll("(.)\\1", "$1*$1");
}
return str;

Explanation of the regex:

The search regex (.)\\1:

(.) means "any character" (the .) and the brackets create a group - group 1 (the first left bracket)
\\1, which in regex is \1 (a java literal String must escape a backslash with another backslash) means "the first group" - this kind of term is called a "back reference"

So together (.)\1 means "any repeated character"

The replacement regex $1*$1:

The $1 term means "the content captured as group 1"

Recursive solution:

Technically, the solution called for on that site is a recursive solution, so here is recursive implementation:

public String pairStar(String str) {
    if (!str.matches(".*(.)\\1.*")) return str;
    return pairStar(str.replaceAll("(.)\\1", "$1*$1"));
}

edited Dec 6, 2012 at 1:42

answered Dec 6, 2012 at 1:22

Bohemian♦

428k103 gold badges604 silver badges750 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Edward Falk Over a year ago

Yeah, I just did about half a dozen puzzles from that site. NONE of them required or even benefited from recursion.

Edward Falk · Accepted Answer · 2012-12-06 18:42:26Z

1

FWIW, here's a non-recursive solution:

public String pairStar(String str) {
  int len = str.length();
  StringBuilder sb = new StringBuilder(len*2);
  char last = '\0';
  for (int i=0; i < len; ++i) {
    char c = str.charAt(i);
    if (c == last) sb.append('*');
    sb.append(c);
    last = c;
  }
  return sb.toString();
}

answered Dec 6, 2012 at 18:42

Edward Falk

10.2k11 gold badges84 silver badges124 bronze badges

Comments

Shiplu Mokaddim · Accepted Answer · 2013-05-08 15:36:53Z

1

I dont know java, but I believe there is replace function for string in java or with regular expression. Your match string would be

([a-z])\\1

And the replace string would be

$1*$1

After some searching I think you are looking for this,

str.replaceAll("([a-z])\\1", "$1*$1").replaceAll("([a-z])\\1", "$1*$1");

edited May 8, 2013 at 15:36

answered Dec 6, 2012 at 1:13

Shiplu Mokaddim

57.5k20 gold badges147 silver badges193 bronze badges

7 Comments

nhahtdh Over a year ago

This solution is wrong, though. Given aaaa, you are supposed to return a*a*a*a

Shiplu Mokaddim Over a year ago

@nhahtdh str.replaceAll("([a-z])\\1", "$1*$1").replaceAll("([a-z])\\1", "$1*$1"); should always work. :)

nhahtdh Over a year ago

Right - it passed the test cases on codingbat. Actually, there is way to solve this with single regex (no loop, no recursion, just a single replaceAll).

Shiplu Mokaddim Over a year ago

@nhahtdh it might be possible. But I am against wasting a lot of time to find a regex. It just time wasting when it takes time to find a good regex while you can do it in trivial way in 10 mins.

nhahtdh Over a year ago

It depends though. I used recursion at first - later when I learn advanced regex, I can write it very quickly. This is not a very practical problem - so I think of it as a challenge of whether some form of solution is possible or not.

|

nhahtdh · Accepted Answer · 2013-05-08 20:04:03Z

This is my own solutions.

Recursive solution (which is probably more or less the solution that the problem is designed for)

public String pairStar(String str) {
    if (str.length() <= 1) return str;
    else return str.charAt(0) +
                (str.charAt(0) == str.charAt(1) ? "*" : "") +
                pairStar(str.substring(1));
}

If you want to complain about substring, then you can write a helper function pairStar(String str, int index) which does the actual recursion work.

Regex one-liner one-function-call solution

public String pairStar(String str) {
  return str.replaceAll("(.)(?=\\1)", "$1*");
}

Both solution has the same spirit. They both check whether the current character is the same as the next character or not. If they are the same then insert a * between the 2 identical characters. Then we move on to check the next character. This is to produce the expected output a*a*a*a from input aaaa.

The normal regex solution of "(.)\\1" has a problem: it consumes 2 characters per match. As a result, we failed to compare whether the character after the 2nd character is the same character. The look-ahead is used to resolve this problem - it will do comparison with the next character without consuming it.

This is similar to the recursive solution, where we compare the next character str.charAt(0) == str.charAt(1), while calling the function recursively on the substring with only the current character removed pairStar(str.substring(1).

Collectives™ on Stack Overflow

Use regex to replace sequences in a string with modified characters

4 Answers 4

Explanation of the regex:

Recursive solution:

1 Comment

Comments

7 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Explanation of the regex:

Recursive solution:

1 Comment

Comments

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related