蓝桥杯入门即劝退（十二）情感丰富的文字

灰太狼 2023-09-23 16:35 38阅读 0赞

**----持续更新蓝桥杯入门系列算法实例------**

**如果你也喜欢Java和算法，欢迎订阅专栏共同学习交流！**

**你的点赞、关注、评论、是我创作的动力！**

\-------希望我的文章对你有所帮助--------

--------------------

**目录**

一、题目描述

代码实现

--------------------

## 一、题目描述 ##

有时候人们会用重复写一些字母来表示额外的感受，比如 `"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`。

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

**示例：**

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

**提示：**

>  *  `1 <= s.length, words.length <= 100`
>  *  `1 <= words[i].length <= 100`
>  *  s 和所有在 `words` 中的单词都只由小写字母组成。

> **解题思路**：1、本题题意 即是从字符串数组中找到若干个可以通过字母扩张得到原字符串的数量
> 
> 2、本题可以使用双指针来完成，即指定 i、j 分别为给定单词以及数组中某个字符串的的指针，指向第一个字符。
> 
> 3、可以编写一个boolean方法来判断符合条件的字符串数量。
> 
> 4、当给定字符小于某个字符串时，即可判断该字符串不可能是符合条件的，直接return。
> 
> 5、设置Count\_s、Count\_t来累积初始两个字符串的相同字母数量
> 
> 6、展开分类讨论，因为如题当s中字母数量小于3时无法扩张，即如果需要符合条件，t字符串中某字母数量需与s相同。
> 
> ![b7176e3755e94cc2ba5b4718a111c68f.jpeg][]
> 
> 7、如果Count\_s小于Count\_t，直接return，如果Count\_s与Count\_t数量不同，且Count\_s<3,即可判断该字符串不合条件。
> 
> 8、最后如果循环结束都为边界值，即比对都符合条件，则为true，否则为false。

## 代码实现 ##

public static int expressiveWords(String s, String[] words) {
            int count=0;
            for (String str:words){
                if (ComPare(s,str))
                    count++;
            }
            return count;
        }
    
        public static boolean ComPare(String s,String t){
            if (s.length()<t.length())
                return false;//长度大于S不合条件
            int i=0,j=0;
            while (i<s.length()&&j<t.length()) {
                if (s.charAt(i) != t.charAt(j))
                    return false;//开始即不相同，不合条件
                
                char ch=s.charAt(i);
                int Count_s=0;
                while (i<s.length()&&s.charAt(i)==ch){
                    ++Count_s;
                    ++i;
                }
                int Count_t=0;
                while (j<t.length()&&t.charAt(j)==ch){
                    ++Count_t;
                    ++j;
                }
                if (Count_t>Count_s)//相同字母大于s相同字母数量，不合条件
                    return false;
                if (Count_s!=Count_t&&Count_s<3)//相同字母数不同，不合条件
                    return false;
            }
            return i==s.length()&&j==t.length();//是否都是到达边界才break？
        }
    }

![3ac3f8d4255d4677980c508eae512f13.png][]

**感谢爱学习的你学到了最后，点个关注、赞支持一下吧！**

[b7176e3755e94cc2ba5b4718a111c68f.jpeg]: https://img-blog.csdnimg.cn/b7176e3755e94cc2ba5b4718a111c68f.jpeg
[3ac3f8d4255d4677980c508eae512f13.png]: https://img-blog.csdnimg.cn/3ac3f8d4255d4677980c508eae512f13.png