Search code examples
stringreturn

Beginners sincerely ask for advice about string

What the class describes is about "reversing a string", which is correct and usable from the Leetcode website. Today, I want to present "reversing a string" by inputting a value by myself (such as the int main() part below), but I still can't execute it after thinking for a long time. Beginners sincerely ask for advice, maybe you can also attach your writing so that I can learn, thank you.

   #include <iostream>
    #include <string>
    using namespace std;
    
    class Solution
    {
    public:
        string reverseWords(string s)
        {
            if (s.size() == 0)
            { 
                return s;
            }
            int front = 0, back = 0; 
            for (int i = 0; i < s.size() - 1; i++)
            {
                if (s[i] != ' ')
                {
                    back++;
                }
                else
                {
                    reverse(s.begin() + front, s.begin() + back); 
                    front = back + 1;                             
                    back = front;                                
                }
            } 
            back++;
            reverse(s.begin() + front, s.begin() + back); 
            return s;
        }
    };
    
    int main()
    {
        Solution word01;
        string s1= "Hello caterpillar";
        word01 s1;
        cout << s1.reverseWords();
    }
Solution

    • Your code is pretty good, however we just want to reverse the words not the chars, for that we can use a while loop.

    • Similarly using two pointers, this'd pass just fine:

    // The following block might trivially improve the exec time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <string>
#include <algorithm>

static const struct Solution {
    using ValueType = std::uint_fast16_t;
    std::string reverseWords(std::string s) {
        std::reverse(std::begin(s), std::end(s));
        ValueType len = std::size(s);
        ValueType index = 0;

        for (auto left = 0; left < len; ++left) {
            if (s[left] != ' ') {
                if (index) {
                    s[index++] = ' ';
                }

                ValueType right = left;

                while (right < len && s[right] != ' ') {
                    s[index++] = s[right++];
                }

                std::reverse(std::begin(s) + index - (right - left), std::begin(s) + index);
                left = right;
            }
        }

        s.erase(std::begin(s) + index, std::end(s));
        return s;
    }
};

    Here is LeetCode's solution with comments:

    class Solution {
  public:
  string reverseWords(string s) {
    // reverse the whole string
    reverse(s.begin(), s.end());

    int n = s.size();
    int idx = 0;
    for (int start = 0; start < n; ++start) {
      if (s[start] != ' ') {
        // go to the beginning of the word
        if (idx != 0) s[idx++] = ' ';

        // go to the end of the word
        int end = start;
        while (end < n && s[end] != ' ') s[idx++] = s[end++];

        // reverse the word
        reverse(s.begin() + idx - (end - start), s.begin() + idx);

        // move to the next word
        start = end;
      }
    }
    s.erase(s.begin() + idx, s.end());
    return s;
  }
};

    References

    • For additional details, please see the Discussion Board where you can find plenty of well-explained accepted solutions with a variety of languages including low-complexity algorithms and asymptotic runtime/memory analysis1, 2.