809. 情感丰富的文字

Medium

题目描述

有时候人们会重复字母来表达额外的情感。例如：

“hello” -> “heeellooo”
“hi” -> “hiiii”

在这些像 “heeellooo” 这样的字符串中，我们有相邻字母都相同的分组：“h”、“eee”、“ll”、“ooo”。

给你一个字符串 s 和一个查询字符串数组 words。如果一个查询单词可以通过以下扩展操作使其等于 s，那么这个查询单词是可扩展的：选择一个由字符 c 组成的分组，向该分组添加一些字符 c，使得该分组的大小变为 3 或更多。

例如，以 “hello” 开始，我们可以对分组 “o” 进行扩展得到 “hellooo”，但我们不能得到 “helloo”，因为分组 “oo” 的大小小于 3。我们也可以进行另一个扩展，如 “ll” -> “lllll” 得到 “helllllooo”。如果 s = "helllllooo"，那么查询单词 “hello” 是可扩展的，因为这两个扩展操作：query = "hello" -> "hellooo" -> "helllllooo" = s。

返回可扩展的查询字符串数量。

示例 1:

输入：s = "heeellooo", words = ["hello", "hi", "helo"]
输出：1
解释：
我们可以扩展单词 "hello" 中的 "e" 和 "o" 得到 "heeellooo"。
我们无法扩展 "helo" 得到 "heeellooo"，因为分组 "ll" 的大小不是 3 或更多。

示例 2:

输入：s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"]
输出：3

提示：

1 <= s.length, words.length <= 100
1 <= words[i].length <= 100
s 和 words[i] 由小写字母组成

解题思路

这道题的核心思路是判断每个查询单词能否通过扩展操作变成目标字符串 s。

解题思路：

分组统计：首先需要将字符串按照连续相同字符进行分组，统计每组字符及其出现次数。
扩展规则理解：
- 只能扩展已有的字符组
- 扩展后的组大小必须≥3
- 不能创建新的字符组
匹配条件：对于查询单词能够扩展成目标字符串，需要满足：
- 两个字符串的字符组序列完全相同（字符类型和顺序）
- 对于每个字符组：
  - 如果目标串中该组大小≥3，查询串中对应组大小可以是1到目标大小之间任意值
  - 如果目标串中该组大小<3，查询串中对应组大小必须完全相等
算法步骤：
- 实现字符串分组函数
- 实现两个分组序列的匹配判断函数
- 遍历所有查询单词，统计可扩展的数量

这种方法时间复杂度合理，逻辑清晰，易于实现和理解。

代码实现

class Solution {
public:
    int expressiveWords(string s, vector<string>& words) {
        auto groups = getGroups(s);
        int count = 0;
        
        for (const string& word : words) {
            if (canStretch(getGroups(word), groups)) {
                count++;
            }
        }
        
        return count;
    }
    
private:
    vector<pair<char, int>> getGroups(const string& s) {
        vector<pair<char, int>> groups;
        int i = 0;
        
        while (i < s.length()) {
            char c = s[i];
            int count = 1;
            
            while (i + count < s.length() && s[i + count] == c) {
                count++;
            }
            
            groups.push_back({c, count});
            i += count;
        }
        
        return groups;
    }
    
    bool canStretch(const vector<pair<char, int>>& word_groups, 
                   const vector<pair<char, int>>& target_groups) {
        if (word_groups.size() != target_groups.size()) {
            return false;
        }
        
        for (int i = 0; i < word_groups.size(); i++) {
            char wc = word_groups[i].first;
            int wcount = word_groups[i].second;
            char tc = target_groups[i].first;
            int tcount = target_groups[i].second;
            
            if (wc != tc) {
                return false;
            }
            
            if (tcount < 3) {
                if (wcount != tcount) {
                    return false;
                }
            } else {
                if (wcount > tcount || wcount < 1) {
                    return false;
                }
            }
        }
        
        return true;
    }
};

class Solution:
    def expressiveWords(self, s: str, words: List[str]) -> int:
        def get_groups(string):
            groups = []
            i = 0
            while i < len(string):
                char = string[i]
                count = 1
                while i + count < len(string) and string[i + count] == char:
                    count += 1
                groups.append((char, count))
                i += count
            return groups
        
        def can_stretch(word_groups, target_groups):
            if len(word_groups) != len(target_groups):
                return False
            
            for (wc, wcount), (tc, tcount) in zip(word_groups, target_groups):
                if wc != tc:
                    return False
                
                if tcount < 3:
                    if wcount != tcount:
                        return False
                else:
                    if wcount > tcount or wcount < 1:
                        return False
            
            return True
        
        target_groups = get_groups(s)
        count = 0
        
        for word in words:
            if can_stretch(get_groups(word), target_groups):
                count += 1
        
        return count

public class Solution {
    public int ExpressiveWords(string s, string[] words) {
        var targetGroups = GetGroups(s);
        int count = 0;
        
        foreach (string word in words) {
            if (CanStretch(GetGroups(word), targetGroups)) {
                count++;
            }
        }
        
        return count;
    }
    
    private List<(char, int)> GetGroups(string s) {
        var groups = new List<(char, int)>();
        int i = 0;
        
        while (i < s.Length) {
            char c = s[i];
            int count = 1;
            
            while (i + count < s.Length && s[i + count] == c) {
                count++;
            }
            
            groups.Add((c, count));
            i += count;
        }
        
        return groups;
    }
    
    private bool CanStretch(List<(char, int)> wordGroups, List<(char, int)> targetGroups) {
        if (wordGroups.Count != targetGroups.Count) {
            return false;
        }
        
        for (int i = 0; i < wordGroups.Count; i++) {
            var (wc, wcount) = wordGroups[i];
            var (tc, tcount) = targetGroups[i];
            
            if (wc != tc) {
                return false;
            }
            
            if (tcount < 3) {
                if (wcount != tcount) {
                    return false;
                }
            } else {
                if (wcount > tcount || wcount < 1) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

var expressiveWords = function(s, words) {
    function getGroups(str) {
        const groups = [];
        let i = 0;
        while (i < str.length) {
            const char = str[i];
            let count = 1;
            while (i + count < str.length && str[i + count] === char) {
                count++;
            }
            groups.push([char, count]);
            i += count;
        }
        return groups;
    }
    
    function isStretchy(word) {
        const sGroups = getGroups(s);
        const wordGroups = getGroups(word);
        
        if (sGroups.length !== wordGroups.length) {
            return false;
        }
        
        for (let i = 0; i < sGroups.length; i++) {
            const [sChar, sCount] = sGroups[i];
            const [wChar, wCount] = wordGroups[i];
            
            if (sChar !== wChar) {
                return false;
            }
            
            if (sCount < wCount) {
                return false;
            }
            
            if (sCount > wCount && sCount < 3) {
                return false;
            }
        }
        
        return true;
    }
    
    return words.filter(isStretchy).length;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值	说明
时间复杂度	O(N × M)	N是words数组长度，M是字符串的平均长度，需要遍历所有单词并对每个单词进行分组和比较
空间复杂度	O(M)	需要存储字符分组信息，M是字符串的平均长度

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析