Burak Dede's Blog

Reverse Words In String Problem - Leetcode

Problem

This is my approach to the solution of reverse words in string problem from Leetcode. https://leetcode.com/problems/reverse-words-in-a-string-iii/description/

  • can we use extra memory, probably not?
  • either way if you take the char[] array out of string you are using extra
  • only one space or multiple spaces between words?
  • Character.isWhitespace is your friend
  • Seems like there is no punctuation between words but it is better to ask if they will be also reversed

First solution comes to my mind is passing through the initial string and each time we pass over complete word (when we spot a space it means it’s a complete word) create reverse function to take care of the reversing individual words. Keep two indexes one for start of the word and other for end of the word. Keep start and move end until you point space, reverse between and update start to be new end. Do this until end of the string.

public String reverseWords(String s) {
    if(s.length() == 0 || s.length() == 1) return s;

    char[] str = s.toCharArray();
    int start = 0;
    int end = start;

    while (end <= str.length - 1) {
        // is not necessary when we have single space but anyway...
        while (end <= str.length - 1 && !Character.isWhitespace(str[end])) {
            end++;
        }

        // end is pointing to space
        reverseBetween(str, start, end -1);
        start = ++end;
    }

    return new String(str);
}

private void reverseBetween(char[] str, int start, int end) {
    int s = start;
    int e = end;
    while(s <= e) {
        swap(str, s, e);
        s++;
        e--;
    }
}

private void swap(char[] str, int first, int second) {
    char tmp = str[first];
    str[first] = str[second];
    str[second] = tmp;
}

For this problem we are using extra memory because Strings are immutable in java and having toCharArray for mutable char[] cause extra memory so I would consider this O(n) space complexity. For time complexity this is O(n) since we iterate over the whole string once.

Seems like Leetcode have different solution especially using builtin split() and similar function I suppose if you know their complexity it’s fine to use builtin methods.