文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

有時候人們會用重復寫一些字母來表示額外的感受，比如 "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 。說明： 0 <= len(S) <= 100。 0 <= len(words) <= 100。 0 <= len(words[i]) <= 100。 S 和所有在 words 中的單詞都只由小寫字母組成。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/expressive-words
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

class Solution { public:int expressiveWords(string S, vector<string>& words) {if(S == "") return 0;int ans = 0, num = 0;vector<char> S_char;//記錄連續的單一字符vector<int> count;//單一字符個數char prev = S[0];for(int i = 0; i < S.size(); i++){if(S[i] != prev){S_char.push_back(prev);count.push_back(num);num = 1;prev = S[i];}else{num++;}}S_char.push_back(prev);count.push_back(num);for(auto& w : words){if(w == "")continue;bool flag = true;int i = 0;num = 0;prev = w[0];// 對每個單詞同樣的方法for(int j = 0; j < w.size(); j++){if(w[j] != prev){if(i == S_char.size() || prev != S_char[i] || count[i] < num|| (count[i] != num && count[i]<3)){// 字符跟S不匹配、S的字符數小于num、個數不等且S中的個數小于3flag = false;//不能得到Sbreak;}i++;num = 1;prev = w[j];}else{num++;}}if(i == S_char.size() || prev != S_char[i] || count[i] < num|| (count[i] != num && count[i]<3))flag = false;if(flag && i == S_char.size()-1)ans++;}return ans;} };

8 ms 7.6 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode 809. 情感丰富的文字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。