2047. 句子中的有效单词数 : 简单字符串模拟

简介: 2047. 句子中的有效单词数 : 简单字符串模拟

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 2047. 句子中的有效单词数 ,难度为 简单


Tag : 「模拟」、「双指针」


句子仅由小写字母('a''z')、数字('0' 到 '9')、连字符('-')、标点符号('!''.'',')以及空格(' ')组成。每个句子可以根据空格分解成 一个或者多个 token ,这些 token 之间由一个或者多个空格 ' ' 分隔。


如果一个 token 同时满足下述条件,则认为这个 token 是一个有效单词:


  • 仅由小写字母、连字符和/或标点(不含数字)。
  • 至多一个 连字符 '-' 。如果存在,连字符两侧应当都存在小写字母("a-b" 是一个有效单词,但 "-ab""ab-" 不是有效单词)。
  • 至多一个 标点符号。如果存在,标点符号应当位于 token 的 末尾 。


这里给出几个有效单词的例子:"a-b.""afad""ba-c""a!""!"


给你一个字符串 sentence ,请你找出并返回 sentence 中 有效单词的数目 。


示例 1:


输入:sentence = "cat and  dog"
输出:3
解释:句子中的有效单词是 "cat"、"and" 和 "dog"
复制代码


示例 2:


输入:sentence = "!this  1-s b8d!"
输出:0
解释:句子中没有有效单词
"!this" 不是有效单词,因为它以一个标点开头
"1-s" 和 "b8d" 也不是有效单词,因为它们都包含数字
复制代码


示例 3:


输入:sentence = "alice and  bob are playing stone-game10"
输出:5
解释:句子中的有效单词是 "alice"、"and"、"bob"、"are" 和 "playing"
"stone-game10" 不是有效单词,因为它含有数字
复制代码


示例 4:


输入:sentence = "he bought 2 pencils, 3 erasers, and 1  pencil-sharpener."
输出:6
解释:句子中的有效单词是 "he"、"bought"、"pencils,"、"erasers,"、"and" 和 "pencil-sharpener."
复制代码


提示:


  • 1 <= sentence.length <= 10001<=sentence.length<=1000
  • sentence 由小写英文字母、数字(0-9)、以及字符(' ''-''!''.' 和 ',')组成
  • 句子中至少有 11token


模拟



根据题意进行模拟即可,先将 sentence 按照空格进行分割,得到多个 item,再对每个 item 进行合法性检查,最后统计合法的 item 个数即为答案。


在对 item 进行合法性检查时,分别使用 c1c1c2c2 代表「连字符」和「标点符号」的出现次数。


特别说明:Java 的 split 操作基于正则,复杂度为线性,其他语言可能需要使用「双指针」手写 split 操作


代码( 双指针实现 split 的代码见 P2P2 ):


class Solution {
    public int countValidWords(String sentence) {
        String[] ss = sentence.split(" ");
        int ans = 0;
        for (String s : ss) if (check(s)) ans++;
        return ans;
    }
    boolean check(String s) {
        int n = s.length();
        if (n == 0) return false;
        for (int i = 0, c1 = 0, c2 = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) return false;
            if (c == ' ') return false;
            if (c == '-' && ++c1 >= 0) {
                if (c1 > 1 || (i == 0 || i == n - 1)) return false;
                if (!Character.isLetter(s.charAt(i - 1)) || !Character.isLetter(s.charAt(i + 1))) return false;
            }
            if ((c == '!' || c == '.' || c == ',') && ++c2 >= 0) {
                if (c2 > 1 || (i != n - 1)) return false;
            }
        }
        return true;
    }
}
复制代码

class Solution {
    public int countValidWords(String sentence) {
        int n = sentence.length(), ans = 0;
        for (int i = 0; i < n; ) {
            if (sentence.charAt(i) == ' ' && ++i >= 0) continue;
            int j = i;
            while (j < n && sentence.charAt(j) != ' ') j++;
            if (check(sentence.substring(i, j))) ans++;
            i = j + 1;
        }
        return ans;
    }
    boolean check(String s) {
        int n = s.length();
        if (n == 0) return false;
        for (int i = 0, c1 = 0, c2 = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) return false;
            if (c == ' ') return false;
            if (c == '-' && ++c1 >= 0) {
                if (c1 > 1 || (i == 0 || i == n - 1)) return false;
                if (!Character.isLetter(s.charAt(i - 1)) || !Character.isLetter(s.charAt(i + 1))) return false;
            }
            if ((c == '!' || c == '.' || c == ',') && ++c2 >= 0) {
                if (c2 > 1 || (i != n - 1)) return false;
            }
        }
        return true;
    }
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:执行过程会产生若干子串,子串总长度与 s 相同。复杂度为 O(n)O(n)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.2047 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
算法 C语言 C++
二叉树三种遍历(动态图+代码深入理解)
二叉树三种遍历(动态图+代码深入理解)
2909 3
二叉树三种遍历(动态图+代码深入理解)
|
6月前
|
小程序 UED
拓展校友网络的创新解决方案:校园论坛圈子小程序+跑腿+二手市场系统
这是一款基于小程序的校园跑腿服务平台,支持多种注册登录方式、下单支付、跑腿接单配送、订单跟踪评价及物流查询功能,并配备客服模块提升用户体验。系统包含用户、客服、物流、跑腿员和订单五大核心模块,功能完善。此外,平台还拓展了校友网络功能,如信息咨询发布、校园社区建设和活动组织等,旨在增强校友互动与联系,形成紧密的校友生态。
168 4
|
9月前
|
Web App开发 搜索推荐 开发者
浏览器插件上架指南:如何把你的产品搬上浏览器插件市场
在实践了 Chrone、Firefox、Edge、Opera 等 几个主要的插件平台的上架发布工作后,我觉得很有必要把这个过程和思考记录下来,分享给大家,希望能提供一些参考和避坑的经验。我想通过这篇文章,和大家聊聊「为什么我要做这件事」,以及「这个系列文章会包含哪些内容」。我想用一个系列的文章,记录我是如何把 EmojiClick 搬到浏览器插件市场的,也给大家提供一些借鉴经验。
249 19
|
10月前
|
人工智能 运维 监控
阿里云ACK容器服务生产级可观测体系建设实践
本文整理自2024云栖大会冯诗淳(花名:行疾)的演讲,介绍了阿里云容器服务团队在生产级可观测体系建设方面的实践。冯诗淳详细阐述了容器化架构带来的挑战及解决方案,强调了可观测性对于构建稳健运维体系的重要性。文中提到,阿里云作为亚洲唯一蝉联全球领导者的容器管理平台,其可观测能力在多项关键评测中表现优异,支持AI、容器网络、存储等多个场景的高级容器可观测能力。此外,还介绍了阿里云容器服务在多云管理、成本优化等方面的最新进展,以及即将推出的ACK AI助手2.0,旨在通过智能引擎和专家诊断经验,简化异常数据查找,缩短故障响应时间。
阿里云ACK容器服务生产级可观测体系建设实践
|
9月前
|
人工智能 算法 Serverless
《主动式智能导购AI助手构建》解决方案用户评测
在部署体验过程中,官方提供的详尽文档和图表帮助新手轻松上手,但环境变量设置等问题仍需改进。解决方案采用Multi-Agent架构,百炼大模型实现精准推荐,函数计算优化响应速度。生产环境部署指导全面,但仍需加强异常处理和面向新手的教学资源。整体架构清晰高效,建议完善数据流描述及Router Agent算法逻辑的阐述。
223 10
《主动式智能导购AI助手构建》解决方案用户评测
|
自然语言处理 语音技术 开发者
ChatTTS超真实自然的语音合成模型
ChatTTS超真实自然的语音合成模型
408 3
|
人工智能 小程序 IDE
编一个自己的万年历
编一个自己的万年历
238 2
|
机器学习/深度学习 自然语言处理 搜索推荐
探索文本向量化的新高峰:合合信息acge_text_embedding 模型原创
文本向量化方法包括词袋模型、TF-IDF、词嵌入和预训练模型(如BERT、GPT)。词嵌入如Word2Vec、GloVe和FastText捕捉单词语义,预训练模型则保留上下文信息。C-MTEB是中文文本嵌入评估平台,测试模型在检索、相似性、分类等任务的性能。合合信息的acge_text_embedding模型在C-MTEB中表现优秀,适用于情感分析、文本生成等任务,具有高分类聚类准确性、资源效率和场景适应性。技术突破涉及数据集优化、模型训练策略和持续学习,提供Demo展示如何使用acge模型计算句子相似度。acge_text_embedding是提升文本处理效率和智能化的有力工具。
1321 2
探索文本向量化的新高峰:合合信息acge_text_embedding 模型原创
|
存储 监控 安全
如何在iPhone设备中查看崩溃日志
如何在iPhone设备中查看崩溃日志
303 1
|
网络协议 测试技术 网络安全
2021年中职“网络安全“江西省赛题—B-9:Windows操作系统深入测试
2021年中职“网络安全“江西省赛题—B-9:Windows操作系统深入测试
193 0