文章目錄
- 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中的個數小于3
flag = false;//不能得到S
break;
}
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阿明），一起加油、一起學習進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/208930.html
標籤：其他
上一篇：從小白到高級工程師，打工人的介面測驗神器 Jmeter 如何實作測驗關聯
下一篇：網路篇 思科發現協議CDP-15