Reverse words in Java

Question

Short and Spicy question is that If input is how are you and output should beyou are how.

public class ReverseWord {
 public static void main(String[] args) throws IOException{
 String input;
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 System.out.println("Enter the input string");
 input = br.readLine();
 System.out.println("Enterd String:"+input);
 System.out.println("Reversed:"+reverse(input));
 }
 public static String reverse(String input){
 String delimiter = " ";
 String[] splits = input.split(delimiter);
 String reverse = new String("");
 for(int i=splits.length-1; i>=0; i--){
 //System.out.println(splits[i]);
 reverse += splits[i];
 reverse = reverse.concat(delimiter);
 }
 System.out.println(reverse);
 return reverse;
 }
}

How can I improve my code? And Is there any other way to do it with less time and space complexity?

• Walfrat: for a lot of concatenation, it's better to use a StringBuilder performance wise (time/memory).
• Spotted: How reverse should behave if input isn't how are you ?

Answer 1

The odd behaviour is that the result gets printed twice: once in reverse(), and again in main(). reverse() should be fixed so that it returns the result without printing it.

The output will also include an extra space at the end. It may be invisible, but I would consider it technically incorrect.

Your code, with those issues fixed, and a few tweaks:

public static String reverse(String input) {
 String delimiter = " "; 
 String[] splits = input.split(delimiter);
 String reverse = ""; // Same as new String("")
 for (int i = splits.length - 1; i > 0; i--) { // Be more generous with spaces
 reverse += splits[i] + delimiter; // Get rid of .concat()
 }
 if (splits.length > 0) {
 reverse += splits[0];
 }
 return reverse;
}

However, repeated string concatenation is inefficient: every += involves allocating a new buffer and copying everything. You should really be using a StringBuilder, like this. (Other suggested solutions in that question are also quite good. You should study those answers and form your own opinion.)

• Gibbs: Thanks Sir. It is really helpful. But I don't understand the reason to get rid of concat. please explain
• 200_success: What I mean is that .concat() is more commonly and succinctly written as +.

Answer 2

There are variety of ways of doing it.

If you want to use library methods, then here is a short solution:-

public static String reverse(String input) {
 String[] words = input.trim().split(" ");
 Collections.reverse(Arrays.asList(words));
 return String.join(" ", words);
}

If you want to do most of the stuff by yourself, which probably would be faster(tested on 22 test cases), then here is another solution:-

public String reverse(String s) {
 s = s.trim();
 char[] str = s.toCharArray();
 // first reverse the entire array
 reverseHelper(str,0,str.length -1);
 int cur = 0, i = 0, start = 0, end =0;
 while( i < str.length){
 while( i < str.length && str[i] == ' ') i++;
 start = i;
 while(i < str.length && str[i] != ' ') i++;
 end = i-1;
 // now reverse each word separately
 reverseHelper(str,start, end);
 // this makes sure that the multiple spaces are removed
 //"how are you" is converted to "you are how"
 for(int a = cur, b = start; b <= end; a++, b++)
 str[a] = str[b];
 cur = cur + end - start +2;
 if(cur -1 <str.length )
 str[cur - 1] = ' ';
 }
 while(cur < s.length()){
 str[cur++] = ' '; 
 }
 String result = new String(str);
 return result.trim();
}
private static void reverseHelper(char[] s, int a, int b) {
 for(int i = a, j = b; i < j ; i++, j--){
 char c = s[i];
 s[i] = s[j];
 s[j] = c;
 }

• Gibbs: Thanks. You said that you tested on 22 cases. how did you do these tests? Any tools? Or just by checking the console to know the run time.
• Boris the Spider: I'm not sure speed is the point here - the user input would definitely be the bottleneck... Further, how did you benchmark this? Using a benchmarking framework like JMH or by hand? If the latter, then the numbers are likely wrong anyway...
• maxomax: I tested it by running on this Online Judge leetcode.com/problems/reverse-words-in-a-string Since this website is quite reliable, I assume that their test cases are far better than what I could have come up with.

Answer 3

Although I like @maxomax answer and prefer to let the Lava libraries do what they are good at. Below is my answer without the libraries.

Things I changed.

• Moved the delimiter to private static final
• Added finally block to close the BufferedReader

• Used StringBuilder with a predetermined size.

  public class ReverseWord
  {
   private static final String DELIMITER = " ";
   public static void main(String[] args) throws IOException
   {
   String input;
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.println("Enter the input string");
   try
   {
   input = br.readLine().trim();
   System.out.println("Enterd String:" + input);
   System.out.println("Reversed:" + reverse(input));
   }
   finally
   {
   br.close();
   }
   }
   public static String reverse(String input)
   {
   String[] splits = input.split(DELIMITER);
   StringBuilder reverse = new StringBuilder(input.length() + 1);
   for(int i=splits.length-1; i>=0; i--)
   {
   reverse.append(splits[i]).append(DELIMITER);
   }
   return reverse.toString().trim();
   }
  }
  

• Gibbs: Thanks. I understand first two points. What difference will be there by adding capacity to StringBuilder? Please tell me
• ndrone: It's for the capacity of letters the string builder can handle. Every time you call .append() it checks the size, if it's not enough it news up the object causing more gc's and more cycles. StringBuffer does the same and since string concats use StringBuffer under the covers... well it just speeds up processing and gc's so if you know your capacities use them. Same for any of the Collection API's and arrays.