Win a copy of The Little Book of Impediments (e-book only) this week in the Agile and Other Processes forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Reverse and Replace a String in Linear Time

 
Colin Cruise
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It would be much appreciated if I could have some help with the following problem. I would like to write a Java function that has the following interface:
public String reverseAndReplace(String original, String toBeReplaced, String replacement) { .. }

This method would do two things:
1) Reverse the words in the string.
For example, given the string: "Wealth is the product of man's capacity to think." The method would transform this sentence to: "think. to capacity man's of product the is Wealth"
2) Replace a word in the String with another word.
For example:
public String reverseAndReplace("Wealth is the product of man's capacity to think.", "think", "act");
The method would return: "act. to capacity man's of product the is Wealth"

This method should run in linear time, and it cannot use not any of Java's built-in string manipulation functions nor any third-party packages (such as Apache's StringUtils and the String.replaceAll methods) in its implementation. For example, this is illegal:

public String reverseAndReplace(String original, String toBeReplaced, String replacement) {
return StringUtils.reverseDelimited(original.replaceAll(toBeReplaced, replacement), ' ');
}

Any help would be much appreciated and thanks in advance.
 
Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15641
47
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello Colin, welcome to JavaRanch.

This sounds like a homework question. We love helping people learn Java, but if we would do your homework for you, you'd not learn anything. So, please tell us what you tried yourself and where you get stuck, and then we can help you over the bumps.
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[Colin]: This method should run in linear time,

That part is relatively easy. I recommend you ignore it at first. Chances are good that a naive implementation will run in linear time anyway. Just focus on getting some sort of answer for the problem, first. Refine it later if necessary.

[Colin]: and it cannot use not any of Java's built-in string manipulation functions

Well, that's more of a problem. You need to use some sort of built-in functions here, or you can't possibly access any of the data inside the String. I don't know which are considered "string manipulation functions". This is an ambiguous requirement. I suggest you use something simple like toCharArray(), just once. After that, you're not dealing with a String, but a char[]. Most of the string manipulation you do will be without any help from the class.
 
Colin Cruise
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I tried something like this below, but I am having problems with boundary cases, particularly where the sentence ends with a period. Somehow, I have a feeling that I am not approaching this in the right way. Any help would be much appreciated. Thanks.

public String reverseAndReplace(String original, String toBeReplaced, String replacement) {
String temp="";
String finalString="";
for(int i = 0; i < original.length(); i++) {
char c = original.charAt(i);
if(c == ' ') {
if(temp.equals(toBeReplaced)) {
finalString = replacement + " " + finalString;
} else {
finalString = temp + " " + finalString;
}
temp = "";
} else {
temp += c;
}
if(i == original.length() - 1)
if(temp.equals(toBeReplaced)) {
finalString = replacement + " " + finalString;
} else {
finalString = temp + " " + finalString;
}

}
return finalString;
}
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic