每日一题:LeetCode:2047.句子中的有效单词数

浏览次数 : 次 2022-01-27

博文字数统计 : 647字 | 阅读所需时长 : 2分

× 文章目录

1. 2022-01-26：LeetCode：2047.句子中的有效单词数
1. 1.1. 1. 题目描述
2. 1.2. 2. 方法一：模拟

每日一题：LeetCode：2047.句子中的有效单词数
- 时间：2022-01-27
- 力扣难度：Easy
- 个人难度：Easy
- 数据结构：字符串
- 算法：模拟、数学

2022-01-26：LeetCode：2047.句子中的有效单词数

1. 题目描述

题目：原题链接
- 句子仅由小写字母（’a’ 到 ‘z’）、数字（’0’ 到 ‘9’）、连字符（’-‘）、标点符号（’!’、’.’ 和 ‘,’）以及空格（’ ‘）组成。
- 每个句子可以根据空格分解成一个或者多个 token ，这些 token 之间由一个或者多个空格 ‘ ‘ 分隔。
- 如果一个 token 同时满足下述条件，则认为这个 token 是一个有效单词：
  - 仅由小写字母、连字符和/或标点（不含数字）。
  - 至多一个连字符 ‘-‘ 。如果存在，连字符两侧应当都存在小写字母（”a-b” 是一个有效单词，但 “-ab” 和 “ab-“ 不是有效单词）。
  - 至多一个标点符号。如果存在，标点符号应当位于 token 的末尾。
- 这里给出几个有效单词的例子：”a-b.”、”afad”、”ba-c”、”a!” 和 “!” 。
- 给你一个字符串 sentence ，请你找出并返回 sentence 中有效单词的数目。
- 1 <= sentence.length <= 1000
- 句子中至少有 1 个 token
输入输出规范
- 输入：句子字符串
- 输出：有效单词个数
输入输出示例
- 输入：sentence = “cat and dog”
- 输出：3

2. 方法一：模拟

思路
- 根据题意直接进行模拟
- 单词无效对应以下几种情况
  - 单词中包含数字
  - 单词中包含两个以上连字符
  - 连字符在单词头部或者单词末尾
  - 连字符的左/右边字符不是小写字母
  - 单词中的标点符号不在单词的末尾

题解

public int countValidWords(String sentence) {
    if (sentence == null || sentence.length() == 0) return 0;
    int n = sentence.length();
    int count = 0;
    int left = 0, right = 0;
    while (true) {
        // 删除开头的空格
        while (left < n && sentence.charAt(left) == ' ') left++;
        if (left >= n) break;
        right = left + 1;
        // 找到单词
        while (right < n && sentence.charAt(right) != ' ') right++;
        if (isValid(sentence.substring(left, right))) count++;
        left = right + 1; // 去寻找下一个单词
    }
    return count;
}

private boolean isValid(String word) {
    int n = word.length();
    int hyphenCount = 0, markCount = 0;
    for (int i = 0; i < n; i++) {
        if (Character.isDigit(word.charAt(i))) return false;
        else if (word.charAt(i) == '-') {
            hyphenCount++;
            if (hyphenCount > 1 || i == 0 || i == n - 1
                || !Character.isLetter(word.charAt(i - 1))
                || !Character.isLetter(word.charAt(i + 1))) {
                return false;
            }
        } else if (word.charAt(i) == '!' || word.charAt(i) == '.' || word.charAt(i) == ',') {
            markCount++;
            if (markCount > 1) return false;
            if (i != n - 1) return false;
        }
    }
    return true;
}

复杂度分析：n 是字符串的长度
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$

本文作者： Chthollists
发布时间： 2022-01-27 21:23:09
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:2047.句子中的有效单词数
本文链接： https://chthollists.github.io/post/491e1772.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！