Is there a better and compact way doesn't use large extra storage space like stack


  • 1
    H
    class Solution {
    public:
        void reverseWords(string &s) {
            string word;
            stack<string> result;
            int i;
            
            word = "";
            for (i = 0; ; ++i) {
            	if (i != 0) {
            	    if (s[i - 1] != ' ' && s[i] == ' ') {
            		    result.push(word);
            		    word = "";
            	    }
            	}
            	if (s[i] == '\0') {
            		if (word == "")
            			break;
            		else {
            			result.push(word);
            			break;
            		}
            	}
            	if (s[i] != ' ') {
            		word += s[i];
            	}
            }
            
            s = "";
            int size = result.size();
    
            if (size != 0) {
            	for (i = 0; i < size; ++i) {
            		if (i == 0) {
            			s = result.top();
            			result.pop();
            		}
            		else {
                		s += " " + result.top();
                		result.pop();
            		}
            	}
            }
            else {
            	s = "";
            }
        }
    };
    

    I use the stack to store every words appear in the string, so is there a way that doesn't use the extra storage space like stack to solve the problem? Maybe it needs to manipulate the origin string but not sure how!


  • 0
    V

    Input string needed to be modified as one need to reverse the input string. This version of algorithm doesn't use stack.

    class Solution 
    {
    public:
        void reverseWords(string &s)
        {
            string word, temp;
            s += ' ';
            for (int i = 0; s[i]; i++)
            {
                if (s[i] != ' ')  //this is the current word
                    word += s[i]; 
                else if (word[0])
                {
                    if (temp[0])  
                        word += ' '; 
                    //append the current word at the beginning of temp
                    temp = word + temp;
                    word = "";
                }
            }
            s = temp;
        }
    };

Log in to reply
 

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