stringtime-complexityreverse

i stuck in leetcode problem 151. Reverse Words in a String


Given an input string s, reverse the order of the words. A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space. Return a string of the words in reverse order concatenated by a single space.

class Solution {

public:

    string reverseWords(string s) {
        string ans;
        int i =0;
        int n = s.size();
        while(i<n)
        {
            while(i<n and s[i]==' ')
                i++;
            if(i>=n)
                break;
            int j =i+1;
            while(j<n and s[j]!=' ')
                j++;
            string word = s.substr(i,j-1);
            if(ans.size()==0)
                ans = word;
            else
                ans = word + " "+ ans;
            i = j+1;
            
        }
        return ans;
    }
};

Expected output-"blue is sky the" my output-"blue is blue sky is th"


Solution

  • You have only one small typo in your code.

    The line

            string word = s.substr(i,j-1);
    

    should be

    std::string word = s.substr(i, j - i);
    

    So you mixed up i with 1.

    No big deal.

    #include <string>
    #include <iostream>
    
    std::string reverseWords(std::string s) {
        std::string ans;
        int i = 0;
        int n = s.size();
        while (i < n)
        {
            while (i < n and s[i] == ' ')
                i++;
            if (i >= n)
                break;
            int j = i + 1;
            while (j < n and s[j] != ' ')
                j++;
            std::string word = s.substr(i, j - i);
            if (ans.size() == 0)
                ans = word;
            else
                ans = word + " " + ans;
            i = j + 1;
    
        }
        return ans;
    }
    int main() {
        std::cout << reverseWords("ab cd ef");
    }