8
\$\begingroup\$

I've been trying to learn Java and one way I've been teaching myself is by tackling "programming challenge questions".

One such question is "reverse the character order of words in a string".

For example, " I have a hat " => " I evah a tah " (note the spaces). In my implementation, I don't deal with punctuation, so "I have a hat!" => "I evah a !tah".

I've written an implementation and I'd like some feedback, particularly regarding the readability and efficiency of the code (basically, is there a slicker implementation of what I'm trying to accomplish - to me, the answer is yes, especially the last part of my implementation).

The implementation is basically doing the following:

  • Create a one element-sized String array called candidateReversedWordsString and initialize it with the input String
  • Create a StringBuilder that will build all the reversed words.
  • Iterate through the characters in the string
  • If the character is not a space and the StringBuilder is empty, note the character index value in the wordStartIndex variable and add the character to the StringBuilder.
  • If the character is not a space and the StringBuilder is not empty, add the character to the StringBuilder
  • If the character is a space and the StringBuilder is not empty, take the only element in the candidateReversedWordsString array and basically concatenate the element with the reversed word from the StringBuilder using substrings.
  • If at the final character and the StringBuilder is not empty, slight adjustment to the concatenation
public String reverseWordsInString(final String string) {
    final String[] candidateReversedWordsString = new String[1];
    candidateReversedWordsString[0] = string;
    int stringCharacterIndex = 0;
    int wordStartIndex = 0;
    final StringBuilder reverseWordStringBuilder = new StringBuilder();
    while (stringCharacterIndex < string.length()) {
        if (' ' != string.charAt(stringCharacterIndex)) {
            if (reverseWordStringBuilder.length() == 0) {
                wordStartIndex = stringCharacterIndex;
            }
            reverseWordStringBuilder.append(string.charAt(stringCharacterIndex));
        }

        if (' ' == string.charAt(stringCharacterIndex) && reverseWordStringBuilder.length() > 0) {
            candidateReversedWordsString[0] = new StringBuilder().
                    append(candidateReversedWordsString[0].substring(0, wordStartIndex)).
                    append(reverseWordStringBuilder.reverse().toString()).
                    append(candidateReversedWordsString[0].substring(stringCharacterIndex)).toString();
            reverseWordStringBuilder.setLength(0);
        }

        if (stringCharacterIndex == string.length() - 1 && reverseWordStringBuilder.length() > 0) {
            candidateReversedWordsString[0] = new StringBuilder().
                    append(candidateReversedWordsString[0].substring(0, wordStartIndex)).
                    append(reverseWordStringBuilder.reverse().toString()).toString();
        }
        stringCharacterIndex++;
    }

    return candidateReversedWordsString[0];
}
\$\endgroup\$
5
\$\begingroup\$

I like the effort that you put into naming your variables. You may have gone a bit overboard, though. For example, instead of candidateReversedWordsString, how about result?

A few mechanical issues:

  • This could be a static method, since it relies on no instance state.
  • It's pretty funny that you defined a final String[] of length 1 to store one String with the ability to change its only element. Why not just use a regular String variable?
  • You have…

     int stringCharacterIndex = 0;
     …
     while (stringCharacterIndex < string.length()) {
         …
         stringCharacterIndex++;
     }
    

    That pattern would be easier to understand if written as

    for (int i; i < string.length(); i++) {
        …
    }
    

    Here, I would opt for a short variable name i, which has the connotation of being a loop counter that is an index. string[i] is easy enough to understand.


This statement summarizes your strategic error:

candidateReversedWordsString[0] = new StringBuilder().
        append(candidateReversedWordsString[0].substring(0, wordStartIndex)).
        append(reverseWordStringBuilder.reverse().toString()).
        append(candidateReversedWordsString[0].substring(stringCharacterIndex)).toString();

Basically, you are rebuilding the entire tentative result string every time you want to reverse a word. That's bad for performance, and also complicates your code.

I think that you would be better off without using any StringBuilder, and just using a char[] instead, especially since you know that the result will be exactly the same length as the input.

Consider this solution instead:

public static String reverseWords(String string) {
    char[] c = string.toCharArray();
    int wordStartIndex = -1;
    for (int i = 0; i < c.length; i++) {
        if (c[i] == ' ') {
            // Ignore spaces
            continue;
        }
        if (wordStartIndex < 0) {
            // Mark start of word
            wordStartIndex = i;
        }
        if (i + 1 == c.length || c[i + 1] == ' ') {
            // Word ends here; reverse it
            for (int a = wordStartIndex, b = i; a < b; a++, b--) {
                char swap = c[a];
                c[a] = c[b];
                c[b] = swap;
            }
            wordStartIndex = -1;
        }
    }
    return new String(c);
}
\$\endgroup\$
4
\$\begingroup\$

is there a slicker implementation of what I'm trying to accomplish

"Slicker" is subjective, but this is the approach I would take:

  • When you see a non-whitespace character, push it on a stack
  • When you see a whitespace character (or hit the end of the string), pop all the elements off the stack and onto the StringBuilder

I don't use Java very often, but here is my attempt:

private static String reverseWords(String s) {
  StringBuilder result = new StringBuilder();
  Stack<Character> word = new Stack<>();

  for (char c : s.toCharArray()) {
    if (Character.isWhitespace(c)) {
      while (!word.isEmpty()) {
        result.append(word.pop());
      }

      result.append(c);
    } else {
      word.push(c);
    }
  }

  while (!word.isEmpty()) {
    result.append(word.pop());
  }

  return result.toString();
}

An alternative suggested by @200_success is to replace the stack with a StringBuilder.

private static String reverseWords(String s) {
  StringBuilder result = new StringBuilder();
  StringBuilder word = new StringBuilder();

  for (char c : s.toCharArray()) {
    if (Character.isWhitespace(c)) {
      result.append(word.reverse());
      word.setLength(0);
      result.append(c);
    } else {
      word.append(c);
    }
  }

  return result.append(word.reverse()).toString();
}
\$\endgroup\$
  • 2
    \$\begingroup\$ The StringBuilder code ends up being cleaner, but using a Stack is a beautiful approach! \$\endgroup\$ – Jaime Nov 29 '15 at 14:41
  • \$\begingroup\$ @Jaime Actually, Java programmers tend to shun java.util.Stack because it is poorly designed (it exposes the java.util.Vector methods that it inherits, allowing the stack discipline to be violated) and because it is thread-safe (incurring locking overhead though it is usually not needed). \$\endgroup\$ – 200_success Nov 29 '15 at 17:22
3
\$\begingroup\$

I think your method is unnecessarily cumbersome. It seems more straightforward to have a StringBuilder to which you append a reversed word whenever you find a space. And while I'm not an expert on Java internal workings, it will almost certainly be more efficient:

private StringBuilder appendReversedWord(
    final StringBuilder stringBuilder,
    final CharSequence string,
    final int wordStart,
    final int wordEnd) {
  if (wordEnd > wordStart) {
    stringBuilder
        .append(
            new StringBuilder(wordEnd - wordStart)
            .append(string, wordStart, wordEnd)
            .reverse());
  }
  return stringBuilder;
}

public String reverseWords(final String string) {
  final StringBuilder reversedStringBuilder = new StringBuilder(string.length());
  int stringIndex = 0;
  int wordStartIndex = 0;

  while (stringIndex < string.length()) {
    if (' ' == string.charAt(stringIndex)) {
      appendReversedWord(
          reversedStringBuilder,
          string,
          wordStartIndex,
          stringIndex);
      reversedStringBuilder.append(' ');
      wordStartIndex = stringIndex + 1;
    }
    stringIndex++;
  }

  appendReversedWord(
      reversedStringBuilder,
      string,
      wordStartIndex,
      stringIndex);

  return appendReversedWord.toString();
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.