HOJ.单词统计

题目

一段英语短文的内容记录于 lines 中，每行输入 lines[i] 仅包含 a-z , . , -，即英文小写字母，空格，逗号，句号和续行符。

请统计单词数量：

• - 表示续行符（仅会出现在行尾，且不会出现在最后一行）
• 对于含有续行符的行：将下一行的首个非空字符起的余下部分，拼接在当前行续行符左侧的字符后；
• 对于不含续行符的行：与下一行是分隔的，相当于有一个单词分隔符。

单词：全部由字母组成

其它均为单词分隔符：包括一个或多个连续的空格、逗号、句号 。

输入

• 1 <= lines.length <= 25
• 1 <= lines[i].length <= 80

输出

一个整数，表示所统计的单词数量

算法标签: 模拟, 字符串操作

思路

整体算法分为三步

1. 将带有续行符的单词进行合并
2. 将字符串中的其他分隔符替换为空格， 并将字符串数组合并为一个单词字符串
3. 将处理完的字符串放入$istringstream$进行流式计数

整体算法时间复杂度是$O(n)$, 但是边界情况很多, 实现起来比较复杂

代码

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cctype>

using namespace std;

class Solution {
   
public:
    vector<string> strs;

    void merge(vector<string> &ans) {
   
        int i = 0, n = strs.size();
        while (i < n) {
   
            string s = strs[i];
            i++;
            //对于当前字符串合并所有可能的字符串
            while (true) {
   
                if (strs.empty() || s.back() != '-' || i >= n) break;
                //去除连接符
                s.pop_back();
                string ne_s = strs[i];
                int pos = ne_s.find_first_not_of(' ');
                if (pos != string::npos) s += ne_s.substr(pos);
                else s += ne_s;
                i++;
            }
            ans.push_back(s);
        }
    }

    void handle(string &s, vector<string> &vec) {
   
        for (string &tmp : vec) {
   
            bool pre = true;
            for (char c : tmp) {
   
                if (isalpha(c)) {
   
                    s += c;
                    pre = false;
                }
                else if (!pre) {
   
                    s += ' ';
                    pre = true;
                }
            }
            if (!s.empty() && !pre) s += ' ';
        }
    }


    int GetWordsCnt(const vector<string> &lines) {
   
        strs = lines;
        vector<string> vec;
        merge(vec);

        string s;
        //执行步骤2
        handle(s, vec);

        istringstream is(s);
        string tmp;
        int ans = 0;
        while (is >> tmp) ans++;
        return ans;
    }
};

*后续$AC$代码

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cctype>

using namespace std;

class Solution {
   
public:
    vector<string> strs;

    void merge(vector<string> &ans) {
   
        int i = 0, n = strs.size();
        while (i < n) {
   
            string s = strs[i];
            i++;
            while (true) {
   
                if (strs.empty() || s.back() != '-' || i >= n) break;
                s.pop_back();
                string &ne_s = strs[i];
                int pos = ne_s.find_first_not_of(' ');
                if (pos != string::npos) s += ne_s.substr(pos);
                else s += ne_s;
                i++;
            }
            ans.push_back(s);
        }

    }

    void handle(string &s, vector<string> &vec) {
   
        for (string &tmp : vec) {
   
            //记录前一个位置是否是空格
            bool pre = true;
            for (char c : tmp) {
   
                if (isalpha(c)) {
   
                    s += c;
                    pre = false;
                }
                //当前位置不是字母并且前一个位置不是空格说明是其他的分割符需要转化为空格并且标记当前位置是空格
                else if (!pre) {
   
                    s += ' ';
                    pre = true;
                }
            }
            //字符串不为空并且前面前面没有空格
            if (!s.empty() && !pre) s += ' ';
        }
    }

    int GetWordsCnt(const vector<string> &lines) {
   
        strs = lines;
        vector<string> vec;
        
        merge(vec);
        string s;
        handle(s, vec);

        istringstream is(s);
        string tmp;
        int ans = 0;
        while (is >> tmp) ans++;
        return ans;
    }
};