aspose file tools*
The moose likes Java in General and the fly likes Reverse and Replace a String in Linear Time Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Reverse and Replace a String in Linear Time" Watch "Reverse and Replace a String in Linear Time" New topic
Author

Reverse and Replace a String in Linear Time

Colin Cruise
Greenhorn

Joined: Feb 29, 2008
Posts: 5
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

Joined: Aug 16, 2005
Posts: 14435
    
  23

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.


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 8 API documentation
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
[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

Joined: Feb 29, 2008
Posts: 5
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;
}
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Reverse and Replace a String in Linear Time