title: daily practice (31): flip the word order

categories: [sword finger offer]

tags: [practice every day]

date: 2022/03/05

Daily practice (31): turn the word order

Input an English sentence and flip the order of words in the sentence, but the order of characters in the word remains the same. For simplicity, punctuation is treated like ordinary letters. For example, enter the string "I am a student.", "student. a am I" is output.

Example 1:

Input: "the sky is blue"

Output: "blue is sky the"

Example 2:

Enter: "hello world!"

Output: "world! hello"

Explanation: the input string can contain extra spaces before or after, but the inverted characters cannot be included.

Example 3:

Enter: "a good example"

Output: "example good a"

Explanation: if there is extra space between two words, reduce the space between words after inversion to only one.

explain:

Characters without spaces form a word.

The input string can contain extra spaces before or after, but the inverted characters cannot be included.

If there is extra space between two words, reduce the space between words after inversion to only one.

Source: LeetCode

Link: https://leetcode-cn.com/probl...

Method 1: template code

Method source: https://leetcode-cn.com/probl...

Train of thought analysis

My usual practice and core idea of this kind of topic is to take out all the strings in the sentence and put them into the string array, and then operate the strings in the array and reconnect them. The specific problems and details need to be solved

Analyze according to the requirements of the topic

The idea of traversing a sentence to get a string is to put it into a temporary string when encountering a character. When encountering a space or punctuation (if there is punctuation), the temporary string will be output and cleared

Template code

There are two types of questions that need to be paid attention to: pre and post spaces.

Template 1. If there are pre and post spaces, you must judge that the temporary string is not empty before output, otherwise an empty string will be output

s += " ";    //Here, a space is added to the last character so that the last string will not be missed
string temp = "";   //Temporary string
vector<string> res; //An array of strings
for (char ch : s) { //Traversal character sentence
    if (ch == ' ') {//Space encountered
        if (!temp.empty()) {     //If there are pre and post spaces, it is necessary to judge that the temporary string is not empty. Otherwise, this judgment can be removed
            res.push_back(temp);
            temp.clear();        //Empty temporary string
        }
    } else {
        temp += ch;
    }
}

Template 2. There is no front and rear space, and there is no need to judge the empty string

s += " ";    //Here, a space is added to the last character so that the last string will not be missed
string temp = "";   //Temporary string
vector<string> res; //An array of strings
for (char ch : s) { //Traversal character sentence
    if (ch == ' ') {//Space encountered
        res.push_back(temp);
        temp.clear();        //Empty temporary string
    } else {
        temp += ch;
    }
}

Use: template 1 + invert the entire character array + reconnect

string reverseWords(string s) {
    s += " ";    //Here, a space is added to the last character so that the last string will not be missed
    string temp = "";   //Temporary string
    vector<string> res; //An array of strings
    for (char ch : s) { //Traversal character sentence
        if (ch == ' ') {//Space encountered
            if (!temp.empty()) {     //If there are pre and post spaces, it is necessary to judge that the temporary string is not empty. Otherwise, this judgment can be removed
                res.push_back(temp);
                temp.clear();        //Empty temporary string
            }
        } else {
            temp += ch;
        }
    }
    s.clear();
    reverse(res.begin(), res.end());
    for (string &str : res) {
        s += str + ' ';
    }
    s.pop_back();    //Remove the last space
    return s;
}

Method 2: double pointer

Algorithm flow:

• We use two pointers l and r to help select each word
• In each cycle, first remove the spaces on the right of all words, obtain the rightmost subscript r of a word, and then obtain the leftmost subscript l of a word
• Then add the word s.substr(l + 1, r - l) to ret, and don't forget to add spaces
• Finally, remove the redundant spaces from ret.pop_back()

string reverseWords(string s) {
    int l = 0, r = s.size() - 1;
    string ret;
    while (r >= 0) {
        while (r >= 0 && s[r] == ' ') {
            --r;    //Clear the space to the right of the word
        }
        if (r < 0) {
            break;
        }
        for (l = r; l >=0 && s[l] != ' '; --l);    //Take words
        ret += (s.substr(l + 1, r - l) + " ");
        r = l;
    }
    if (ret.size()) {
        ret.pop_back();  //Remove the last space
    }
    return ret;
}

Method 3: API istringstream

//Stack
string reverseWords(string s) {
    stack<string> stk;
    string res, str;
    istringstream ss(s);
    while (ss >> str) {    //Push 
        stk.push(str),stk.push(" ");
    }
    if (!stk.empty()) {
        stk.pop();
    }
    while (!stk.empty()) {//Out of stack
        res += stk.top(), stk.pop();
    }
    return res;
}
//Non stack
string reverseWords(string s) {
    istringstream ss(s);
    string res, str;
    while ( ss >> str) {
        res = str + ' ' + res;
    }
    return res.substr(0, res.size() - 1);
}