Struggling with String Processing task

[Fred Hamilton]

I've dome my share of string processing, but for some reason I can't get my head around this one. Here is the task.

I start with a string which contains a mixture of letters and 1's. I wish to replace any consecutive subsequence of 1's with a single digit which is equal to the number of 1's in the subsequence.

Now I have an idea about converting the string to a StringBuilder, then iterating through the characters and making the appropriate replacements, seems clear enough. What is not clear to me is as follows

if my for loop is of the form for( int i=0; i<sb.length(); i++ ) {...}, and the length of the StringBuilder decreases within the loop body, will the termination condition of the loop adapt, i.e. is sb.length() re-evaluated with each iteration of the loop?

If anyone has any ideas for a cleaner solution than the one I am considering, I'm all ears.

thanks.

>

[Henry Wong]

Fred Hamilton wrote:if my for loop is of the form for( int i=0; i<sb.length(); i++ ) {...}, and the length of the StringBuilder decreases within the loop body, will the termination condition of the loop adapt, i.e. is sb.length() re-evaluated with each iteration of the loop?

If anyone has any ideas for a cleaner solution than the one I am considering, I'm all ears.

How about, instead of copying the string to the string builder, don't do that part. Only use the string builder for the result. Use the for loop on the string itself, and copy the chars to the builder as you are processing it.


And of course, a simple solution based on regex is possible here too.

Henry

[Abhishk Gupta]

well...I think I have some readymade solution...

private String replaceAll(final String str, final char regex)
    {
        final StringBuilder s = new StringBuilder();
        int count = 0;
        boolean flush = false;
        for (int i = 0; i < str.length(); i++)
        {
            if (regex == str.charAt(i))
            {
                count++;
                flush = true;
            } else
            {
                s.append(str.charAt(i));
                if (flush)
                {
                    s.append(count);
                    count = 0;
                    flush = false;
                }
            }
        }
        return s.toString();
    }

Check if it helps...may be some modifications are required.

[Fred Hamilton]

Henry Wong wrote:

Fred Hamilton wrote:if my for loop is of the form for( int i=0; i<sb.length(); i++ ) {...}, and the length of the StringBuilder decreases within the loop body, will the termination condition of the loop adapt, i.e. is sb.length() re-evaluated with each iteration of the loop?

If anyone has any ideas for a cleaner solution than the one I am considering, I'm all ears.

How about, instead of copying the string to the string builder, don't do that part. Only use the string builder for the result. Use the for loop on the string itself, and copy the chars to the builder as you are processing it.


And of course, a simple solution based on regex is possible here too.

Henry

Thanks Henry, I actually have a solution that does use a second StringBuilder more or less like you suggest, but it's ugly. . But I was looking for something a little cleaner. So the question still remains about whether or not the termination condition will adapt to the changing length of the StringBuilder.

As for the RegEx solution, I tried to think of one but... hmmm... well I suppose I could do a replaceAll, where the replacement string is a method call that returns the string representation of the length of the substring that matches the pattern. I don't know if that would work, but it's worth a try.

p.s Abhishk, thanks for your code, I'll give it a try and let you know ho it goes. It looks very close to the idea I just eplained

[Henry Wong]

Abhishk Gupta wrote:well...I think I have some readymade solution...

Abhishk, it is generally *not* a good idea to give "read made solutions" -- as the JavaRanch is a learning site, and there isn't much learning when you are given the answer.

Fred Hamilton wrote:
Thanks Henry, I actually have a solution that does use a second StringBuilder more or less like you suggest, but it's ugly. . But I was looking for something a little cleaner. So the question still remains about whether or not the termination condition will adapt to the changing length of the StringBuilder.

I can't image it being "ugly". Heck, you don't need a second string buffer -- as the original string can be the source.

Fred Hamilton wrote:
As for the RegEx solution, I tried to think of one but... hmmm... well I suppose I could do a replaceAll, where the replacement string is a method call that returns the string representation of the length of the substring that matches the pattern. I don't know if that would work, but it's worth a try.

If you want to attempt a regex solution, I would recommend that you look at the find(), appendReplacement(), and appendTail() methods. The replaceAll() method is a bit too high level to do this operation efficiently (meaning it won't be able to do this in a single pass).

Henry

[Fred Hamilton]

Henry Wong wrote:

Fred Hamilton wrote:
Thanks Henry, I actually have a solution that does use a second StringBuilder more or less like you suggest, but it's ugly. . But I was looking for something a little cleaner. So the question still remains about whether or not the termination condition will adapt to the changing length of the StringBuilder.

I can't image it being "ugly". Heck, you don't need a second string buffer -- as the original string can be the source.

...

Any thoughts about the termination condition issue? That's the real question here. edit: well maybe not the only question. thanks for the Regex tips

[Henry Wong]

Fred Hamilton wrote:
Any thoughts about the termination condition issue? That's the real question here.

The "terminating condition" is the end of the string. Remember, if you use the original string as the source, and the stringbuffer as the target, the underlying string doesn't change while you are processing it.

Henry

[Abhishk Gupta]

Henry Wong wrote:Abhishk, it is generally *not* a good idea to give "read made solutions" -- as the JavaRanch is a learning site, and there isn't much learning when you are given the answer.

Henry, I am new here so not much aware of the customs of JavaRanch. I have taken a note of the point.
As far as regex solution suggested by you is considered, I am not much comfortable with that.

Henry Wong wrote:
If you want to attempt a regex solution, I would recommend that you look at the find(), appendReplacement(), and appendTail() methods. The replaceAll() method is a bit too high level to do this operation efficiently (meaning it won't be able to do this in a single pass).

I think even this would involve complexities of customizing Matcher and Pattern classes.
This is just my opinion...Please share your thoughts on it.

[Fred Hamilton]

Henry Wong wrote:

Fred Hamilton wrote:
Any thoughts about the termination condition issue? That's the real question here.

The "terminating condition" is the end of the string. Remember, if you use the original string as the source, and the stringbuffer as the target, the underlying string doesn't change while you are processing it.

Henry

Understood, but the original question involved looping on the characters of a StringBuilder, not a string. Thanks anyways for your responses.

Anyways, I came up with the following little algorithm, which seems to work quite nicely and answers "yes" to my question about the termination condition.

int j;
for( int i=0; i<sb.length(); i++ ) {

    if( sb.charAt(i) != '1' ) continue;
    j=0; while( sb.charAt( i+(++j) ) == '1' );
    sb.replace( i, i+j, ""+j );
}

>

[Henry Wong]

Abhishk Gupta wrote:As far as regex solution suggested by you is considered, I am not much comfortable with that.

Henry Wong wrote:
If you want to attempt a regex solution, I would recommend that you look at the find(), appendReplacement(), and appendTail() methods. The replaceAll() method is a bit too high level to do this operation efficiently (meaning it won't be able to do this in a single pass).

I think even this would involve complexities of customizing Matcher and Pattern classes.
This is just my opinion...Please share your thoughts on it.

Since a string to stringbuffer solution has been presented. And since the OP presented a in-place string buffer solution... which is the purpose of this topic. I see no reason to not present a regex solution.


Here is how I would do this problem, using regexes...

public static String process(String s) {
    Matcher m = Pattern.compile("1+").matcher(s);

    StringBuffer r = new StringBuffer();
    while (m.find()) {
        m.appendReplacement(r, Integer.toString(m.group().length()));
    }
    m.appendTail(r);		
    return r.toString();
}

Henry

[Janeice DelVecchio]

I like the stringbuilder idea, but I had another idea that you might consider....

read the string into an arraylist of Integers (i.e. numeric values of the characters for the characters, "1...2..3" etc for the numeric values. then use nested ifs:

//if the integer being read == 1
     // if the last entry < 65 (the first alphabetic value)
          // last entry++

And then to get the data out, cast the int as a character if it falls between 65 and 90.

Or you could fill an arraylist with characters, then iterate through it to find where the 1s are and remove the other entries...

Just a thought.
Janeice

[Abhishk Gupta]

Henry Wong wrote:
Here is how I would do this problem, using regexes...

Loved your solution Henry

[D. Ogranos]

My solution would be

public String process(String s) {
  StringBuilder buf = new StringBuilder();
  int i = 0;
  while (i < s.length()) {
    if (s.charAt(i) == '1') {
      int count = 0;
      while (i < s.length() && s.charAt(i) == '1') {
        count += 1;
        i += 1;
      }
      buf.append(count);
    }
    else {
      buf.append(s.charAt(i));
      i += 1;
    }
  }
  return buf.toString();
}

Should be equivalent to Henry's, except that it is much more efficient. Regular expressions are SLOOOOOOOOOOOW

[Fred Hamilton]

D. Ogranos wrote:My solution would be

public String process(String s) {
  StringBuilder buf = new StringBuilder();
  int i = 0;
  while (i < s.length()) {
    if (s.charAt(i) == '1') {
      int count = 0;
      while (i < s.length() && s.charAt(i) == '1') {
        count += 1;
        i += 1;
      }
      buf.append(count);
    }
    else {
      buf.append(s.charAt(i));
      i += 1;
    }
  }
  return buf.toString();
}

Should be equivalent to Henry's, except that it is much more efficient. Regular expressions are SLOOOOOOOOOOOW

Thanks for this. This looks good to me. I won't comment on the speed of this compared to RegEx, This looks kind of like the solution Henry originally recommended. What do you think of my solution that involves using the replace method and a single stringbuilder. The code is smaller anyways.

Regards.