C/C++ Coding Exercise - Reverse Words in a String - LeetCode Online Judge - Using Stack

Given a string that consists of words (non-space characters count as part of a word), you are required to output the new sentence that reverses the words. For example, ‘the sky is blue’ reversed will become ‘blue is sky the’. If there are continuous multiple white spaces, keep only one space in the result. The leading and trailing zeros are to be removed from the result. The problem is from leetcode online judge.

The approach to solve this puzzle is straightforward, we can split the sentence into words by delimiter ‘whitespace’ and reverse the words using a stack data structure. This is the simplest method and it involves two passes. The first approach is forward, analysing the sentence, splitting into words, which is inserted into stack. The second pass will pop element from the stack one by one, and connect them into a sentence using only 1 space.

class Solution {
public:
    void reverseWords(string &s) {
            stack st;
            int i = 0, k = s.length();
            while (i < k) { // while cursor not reaching the end of sentence
                int j = i;
                while ((s[j] == ' ') && (j < k)) j ++; // skip leading spaces
                if (j == k) break;
                int u = j;
                while ((s[u] != ' ') && (u < k)) u ++; // look for end of word                 
                string sub = s.substr(j, u - j); // get the word                 
                st.push(sub); // push it to stack                 
                i = u; // next word             
            }             
            s = "";             
            if (st.size() == 0) {                               
                return;             
            }             
            // the first reversed word does not have leading white space
            s = st.top();
            st.pop();
            while (st.size() > 0) { // First In Last Out
                string t = st.top();
                st.pop();
                s = s + " " + t;
            }
    }
};

class Solution {
public:
    void reverseWords(string &s) {
            stack st;
            int i = 0, k = s.length();
            while (i < k) { // while cursor not reaching the end of sentence
                int j = i;
                while ((s[j] == ' ') && (j < k)) j ++; // skip leading spaces
                if (j == k) break;
                int u = j;
                while ((s[u] != ' ') && (u < k)) u ++; // look for end of word                 
                string sub = s.substr(j, u - j); // get the word                 
                st.push(sub); // push it to stack                 
                i = u; // next word             
            }             
            s = "";             
            if (st.size() == 0) {                               
                return;             
            }             
            // the first reversed word does not have leading white space
            s = st.top();
            st.pop();
            while (st.size() > 0) { // First In Last Out
                string t = st.top();
                st.pop();
                s = s + " " + t;
            }
    }
};

The leading and trailing zeros should be also removed.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...

421 words
Last Post: Command Line Parameters in VBScript Windows Scripting Host
Next Post: How to Evaluate Reverse Polish Notation using Stack?

The Permanent URL is: C/C++ Coding Exercise – Reverse Words in a String – LeetCode Online Judge – Using Stack