Keshawn_lu's Blog

Leetcode 809. 情感丰富的文字

双指针
字数统计: 616阅读时长: 2 min
2022/11/25 Share

题目简介：

有时候人们会用重复写一些字母来表示额外的感受，比如 "hello" -> "heeellooo", "hi" -> "hiii"。我们将相邻字母都相同的一串字符定义为相同字母组，例如：”h”, “eee”, “ll”, “ooo”。

对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同，我们将这个单词定义为可扩张的（stretchy）。扩张操作定义如下：选择一个字母组（包含字母 c ），然后往其中添加相同的字母 c 使其长度达到 3 或以上。

例如，以 “hello” 为例，我们可以对字母组 “o” 扩张得到 “hellooo”，但是无法以同样的方法得到 “helloo” 因为字母组 “oo” 长度小于 3。此外，我们可以进行另一种扩张 “ll” -> “lllll” 以获得 “helllllooo”。如果 S = "helllllooo"，那么查询词 “hello” 是可扩张的，因为可以对它执行这两种扩张操作使得 query = "hello" -> "hellooo" -> "helllllooo" = S。

输入一组查询单词，输出其中可扩张的单词数量。

示例：

1
2
3
4
5
6
7
输入： 
S = "heeellooo"
words = ["hello", "hi", "helo"]
输出：1
解释：
我们能通过扩张 "hello" 的 "e" 和 "o" 来得到 "heeellooo"。
我们不能通过扩张 "helo" 来得到 "heeellooo" 因为 "ll" 的长度小于 3 。

提示：

  • 0 <= len(S) <= 100。
  • 0 <= len(words) <= 100。
  • 0 <= len(words[i]) <= 100。
  • S 和所有在 words 中的单词都只由小写字母组成。

思路：

双指针，若word与s的大小不同，则直接返回false。

然后判断每次连续字符的个数，若word的连续字符个数大于s，则返回false。

若sum1 != sum2，且s的连续字符个数少于3，则也返回false。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:

    bool solve(string& s, string& word){

        if(word.size() > s.size())
            return false;

        int i = 0;
        int j = 0;

        while(i < s.size()){

            if(s[i] != word[j])
                return false;
            
            int sum1 = 1;
            while(i + 1 < s.size() && s[i] == s[i + 1]){

                sum1++;
                i++;
            }

            int sum2 = 1;
            while(j + 1 < word.size() && word[j] == word[j + 1]){

                sum2++;
                j++;
            }

            if(sum2 > sum1)
                return false;
            
            if(sum1 != sum2 && sum1 < 3)
                return false;

            i++;
            j++;
        }

        return true;
    }

    int expressiveWords(string s, vector<string>& words) {

        int res = 0;
        for(auto& word : words){

            if(solve(s, word))
                res++;
        }

        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网