151/186. Reverse Words in a String I/II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

Could you do it in-place without allocating extra space?

Related problem: 189 Rotate Array
思路:类似翻转array, 注意String是immutable的,只能翻转char array。
1. 先翻转整个char array。
2. 然后遇到’ ‘就翻转前面的部分
3. 翻转最后部分

public class Solution {
    public void reverseWords(char[] s) {
        if (s == null || s.length == 0) return;

        reverseString(0, s.length - 1, s); // reverse whole string
        // reverse by ' '
        int start = 0;
        for (int i = 0; i < s.length; i++) {  // reverse word separated by ' '
            if (s[i] == ' ') {
                reverseString(start, i - 1, s);
                start = i + 1; 
            }
        }
        reverseString(start, s.length - 1, s); // reverse last word

    }

    public void reverseString(int left, int right, char[] s) {
        while(left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
        }
    }
}

151的题目给的是String类型的输入, 注意Java中的String是immutable的,我们需要转换成array来做。做的时候可以split一下,因为可能会出现多个空格,需要正则匹配一下.

public class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        if ( s == null || s.length() == 0) return "";
        String[] words = s.split(" +");
        StringBuilder sb = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) {
            sb.append(words[i].trim());
            if (i != 0) sb.append(" ");
        }
        return sb.toString();
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s