• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Struggling with String Processing task

 
Ranch Hand
Posts: 686
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.

>
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
well...I think I have some readymade solution...

Check if it helps...may be some modifications are required.
 
Fred Hamilton
Ranch Hand
Posts: 686
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 686
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 686
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
>
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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...



Henry
 
Bartender
Posts: 1849
15
Eclipse IDE Spring VI Editor Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:



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
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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



Loved your solution Henry
 
Ranch Hand
Posts: 214
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
My solution would be



Should be equivalent to Henry's, except that it is much more efficient. Regular expressions are SLOOOOOOOOOOOW
 
Fred Hamilton
Ranch Hand
Posts: 686
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

D. Ogranos wrote:My solution would be



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.
 
rubbery bacon. rubbery tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic