In place simple solution


  • 92
    Y

    First, reverse the whole string, then reverse each word.

    void reverseWords(string &s) {
        reverse(s.begin(), s.end());
        int storeIndex = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != ' ') {
                if (storeIndex != 0) s[storeIndex++] = ' ';
                int j = i;
                while (j < s.size() && s[j] != ' ') { s[storeIndex++] = s[j++]; }
                reverse(s.begin() + storeIndex - (j - i), s.begin() + storeIndex);
                i = j;
            }
        }
        s.erase(s.begin() + storeIndex, s.end());
    }

  • 0
    M
    This post is deleted!

  • 0
    G

    Nice soln !!!


  • 0
    This post is deleted!

  • 0
    X

    Nice solution! I do the same thing, except I delete extra space one by one.
    ···
    class Solution {
    public:
    void reverseWords(string &s) {

        int n=s.size();
        reverse(s.begin(),s.end());
        int i=0;
        int l=0,r=0;
        while(i<n){
            if(s[i]==' '){
                if(i>0&&i<n-1&&s[i-1]!=' '&&s[i+1]!=' ')
                   {i++; l=i; r=i;}
                else
                   {s.erase(i,1);n--;}
            }else{
                while(r<n&&s[r]!=' ')
                    r++;
                i=r;
                reverse(s.begin()+l,s.begin()+r);
            }
        }
    }
    

    };


  • 1
    A

    why did the "storeIndex" need?


  • 0
    P

    @a1327793405 Yeah, I don't understand the point of a storeIndex either. Can someone give an example where the code would break without it?


  • -1

    @a1327793405 I think storeIndex is to add the space between two words.


  • -1

    @PraneethVT StoreIndex is to track the end of each word and add a space between two words.


  • 3
    W

    storeIndex basically stores the start position of next word. The new word that I mean is
    space + new word
    except the first word(where storeIdx = 0). Obviously we need a space between two words.

    The procedure inside the for loop is:

    1. put a blank space in front of the word if this word is not the first word
    2. copy the word to the position starts with storeIndex
    3. reverse the word
    4. update the possible start of next word

  • 0
    H

    C Version

    void reverseWord(char*s, int len) {
        char*head = s;
        char*tail = s+len-1;
        char tmp;
        while(head < tail) {
            tmp = *head;
            *head = *tail;
            *tail = tmp;
            head++;
            tail--;
        }
    }
    void reverseWords(char *s) {
        char*s_head = s;
        int s_len = strlen(s);
        char*s_tail = s+s_len - 1;
        int newWordIdx = 0;
        reverseWord(s, s_len);
        while(s <= s_tail) {
            if(*s != ' ') {
                if(newWordIdx != 0)  s_head[newWordIdx++] = ' ';
                char*s_wordTail = s;
                while(*s_wordTail != '\0' && *s_wordTail != ' ') {
                    s_head[newWordIdx++] = *s_wordTail++;
                }
                reverseWord(s_head + newWordIdx -(s_wordTail - s) , s_wordTail - s);
                s = s_wordTail;
            }
            s++;
        }
        s_head[newWordIdx] = '\0';
    }
    
    

  • 0
    Q

    nice solution!
    below is my code, which might be more self-explanatory, with help of a general-purpose trimAll() function, similar to STL algorithm function.

    1. trimAll. trim leading and trailing space, trim inner contiguous spaces to single one.
    2. reverse whole string.
    3. reverse each word.
    void reverseWords(string &s) {
        trimAll(s,' ');
        std::reverse(s.begin(), s.end());
        for (auto first = s.begin(), last = s.end(); ;) {
            auto mid = std::find(first, last, ' ');
            std::reverse(first, mid);
            if (mid == last) break;
            first = ++mid;
        }
    }
    

    for those who might be interested with trimAll(). here it is. A clean C++ solution, 7 lines client code, given an implementation of trimAll().


  • 5
    Y

    Great solution!
    However, it is regret there is no more explanation.Thus, I add some comment about the variables in your code:
    storeIdx: the current position available for insertion.
    j: the end of one word(including one trailing space), used for copying word one by one.
    i: the beginning of one word.

    The procedure inside the for loop is summaried by @wen_chieh in his post, which quotes:

    • put a blank space in front of the word if this word is not the first word

    • copy the word to the position starts with storeIndex

    • reverse the word

    • update the possible start of next word

    Here is the Java solution based on your idea: One should note that C++ std::reverse() reverses the order of the elements in the range [first, last), which is different from self-implemented reverse();

    public String reverseWords(String s) {
            if (s.length() < 1) return s; // empty string
            int startIdx = 0;
            char[] str = s.toCharArray();
            // reverse whole string
            reverse(str, 0, str.length - 1);
            // reverse word one by one
            for (int i = 0; i < str.length; i++) {
                if (str[i] != ' ') {
                    if (startIdx != 0) str[startIdx++] = ' ';
                    int j = i;
                    while (j < str.length && str[j] != ' ')
                        str[startIdx++] = str[j++];
                    reverse(str, startIdx - (j - i), startIdx - 1); // startIdx - 1, NOT startIdx; 
                    // C++ std::reverse : Reverses the order of the elements in the range [first, last)
                    i = j;
                }
            }
            return new String(str, 0, startIdx);
        }
    
        private void reverse(char[] str, int begin, int end) {
            for (; begin < end; begin++, end--) {
                char tmp = str[begin];
                str[begin] = str[end];
                str[end] = tmp;
            }
        }
    

  • 0
    L

    Straightforwardly erase spaces in place one by one.

        void reverseWords(string &s) {
            while(s[0]==' ') s.erase(0,1);  //erase leading and trailing spaces
        	reverse(s.begin(),s.end());
        	while(s[0]==' ') s.erase(0,1);
        	
        	int b=0, e=0;  // begin and end of a word
            for(e=0;e<s.length();e++)
                if(s[e]==' ') {
        		reverse(s.begin()+b, s.begin()+e);
        		while(s[e+1]==' ') s.erase(e+1,1);
        		b=e+1;
        	     }
            reverse(s.begin()+b, s.end());
        }
    

  • 1
    G

    Dealing with the blank spaces in this way. Pretty similar solution

           StringBuilder sb = new StringBuilder();
            if(s == null || s.length()==0) return sb.toString();
           
           //Removing Anything Apart from a-zA-Z0-9 using the Regular Expressions 
           String reg = "[^a-zA-Z0-9]+";
           if (s.matches(reg)) return sb.toString();
           
           //Removing the end spaces using the trim and split("\\s+") to remove bunnch of consistent white spaces.
           String [] str = s.trim().split("\\s+");
           for(int i =str.length-1 ; i>=0 ; i--){
               sb.append(str[i]);
               sb.append(" ");
           }
           //To remove the last the " " provided to the function
           return sb.toString().trim();
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.