0809-情感丰富的文字

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

有时候人们会用重复写一些字母来表示额外的感受，比如 "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 中的单词都只由小写字母组成。

方法一：双指针

思路与算法

我们可以依次判断数组 words 中的每一个字符串是否可以扩张成给定的字符串 s。

假设我们需要判断 t 是否可以扩张成 s，我们可以使用双指针来解决这个问题。两个指针 i 和 j 初始时分别指向字符串 s 和 t 的首个位置。在双指针遍历的过程中：

  • 首先我们需要保证 s[i] = t[j]，否则这两部分不是相同的字母，无法进行扩张；

  • 随后我们不断地向右移动两个指针，直到移动到与之前不同的字母，或者超出字符串的边界。假设字符串 s 有 cnt}_i 个相同的字母，t 有 cnt}_j 个相同的字母，那么我们必须保证 cnt}_i \geq \textit{cnt}_j，因为扩张不可能减少字符的数量。当 cnt}_i = \textit{cnt}_j 时，我们无需进行扩张，这样也是满足要求的；cnt}_i > \textit{cnt}_j，由于扩张至少会达到长度 3 及以上，因此需要保证 cnt}_i \geq 3 即可。

当某一个指针超出边界时，我们就可以退出上述的遍历过程。此时，如果另一个指针也超出边界，说明两个字符串同时遍历完成，即 t 可以扩张成 s。

代码

[sol1-C++]
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
class Solution {
public:
    int expressiveWords(string s, vector<string>& words) {
        int ans = 0;
        for (const string& word: words) {
            if (expand(s, word)) {
                ++ans;
            }
        }
        return ans;
    }

private:
    bool expand(const string& s, const string& t) {
        int i = 0, j = 0;
        while (i < s.size() && j < t.size()) {
            if (s[i] != t[j]) {
                return false;
            }
            char ch = s[i];
            int cnti = 0;
            while (i < s.size() && s[i] == ch) {
                ++cnti;
                ++i;
            }
            int cntj = 0;
            while (j < t.size() && t[j] == ch) {
                ++cntj;
                ++j;
            }
            if (cnti < cntj) {
                return false;
            }
            if (cnti != cntj && cnti < 3) {
                return false;
            }
        }
        return i == s.size() && j == t.size();
    }
};
[sol1-Java]
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
class Solution {
    public int expressiveWords(String s, String[] words) {
        int ans = 0;
        for (String word : words) {
            if (expand(s, word)) {
                ++ans;
            }
        }
        return ans;
    }

    private boolean expand(String s, String t) {
        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 cnti = 0;
            while (i < s.length() && s.charAt(i) == ch) {
                ++cnti;
                ++i;
            }
            int cntj = 0;
            while (j < t.length() && t.charAt(j) == ch) {
                ++cntj;
                ++j;
            }
            if (cnti < cntj) {
                return false;
            }
            if (cnti != cntj && cnti < 3) {
                return false;
            }
        }
        return i == s.length() && j == t.length();
    }
}
[sol1-C#]
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
public class Solution {
    public int ExpressiveWords(string s, string[] words) {
        int ans = 0;
        foreach (string word in words) {
            if (Expand(s, word)) {
                ++ans;
            }
        }
        return ans;
    }

    private bool Expand(string s, string t) {
        int i = 0, j = 0;
        while (i < s.Length && j < t.Length) {
            if (s[i] != t[j]) {
                return false;
            }
            char ch = s[i];
            int cnti = 0;
            while (i < s.Length && s[i] == ch) {
                ++cnti;
                ++i;
            }
            int cntj = 0;
            while (j < t.Length && t[j] == ch) {
                ++cntj;
                ++j;
            }
            if (cnti < cntj) {
                return false;
            }
            if (cnti != cntj && cnti < 3) {
                return false;
            }
        }
        return i == s.Length && j == t.Length;
    }
}
[sol1-Python3]
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
class Solution:
    def expressiveWords(self, s: str, words: List[str]) -> int:
        def expand(s: str, t: str) -> bool:
            i = j = 0
            while i < len(s) and j < len(t):
                if s[i] != t[j]:
                    return False
                ch = s[i]
                cnti = 0
                while i < len(s) and s[i] == ch:
                    cnti += 1
                    i += 1
                cntj = 0
                while j < len(t) and t[j] == ch:
                    cntj += 1
                    j += 1
                
                if cnti < cntj:
                    return False
                if cnti != cntj and cnti < 3:
                    return False
            
            return i == len(s) and j == len(t)
        
        return sum(int(expand(s, word)) for word in words)
[sol1-C]
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
bool expand(const char *s, const char *t) {
    int i = 0, j = 0;
    while (s[i] != '\0' && t[j] != '\0') {
        if (s[i] != t[j]) {
            return false;
        }
        char ch = s[i];
        int cnti = 0;
        while (s[i] != '\0' && s[i] == ch) {
            ++cnti;
            ++i;
        }
        int cntj = 0;
        while (t[j] != '\0' && t[j] == ch) {
            ++cntj;
            ++j;
        }
        if (cnti < cntj) {
            return false;
        }
        if (cnti != cntj && cnti < 3) {
            return false;
        }
    }
    return s[i] == '\0' && t[j] == '\0';
}

int expressiveWords(char * s, char ** words, int wordsSize){
    int ans = 0;
    for (int i = 0; i < wordsSize; i++) {
        if (expand(s, words[i])) {
            ++ans;
        }
    }
    return ans;
}
[sol1-JavaScript]
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
var expressiveWords = function(s, words) {
    let ans = 0;
    for (const word of words) {
        if (expand(s, word)) {
            ++ans;
        }
    }
    return ans;
}

const expand = (s, t) => {
    let i = 0, j = 0;
    while (i < s.length && j < t.length) {
        if (s[i] !== t[j]) {
            return false;
        }
        const ch = s[i];
        let cnti = 0;
        while (i < s.length && s[i] === ch) {
            ++cnti;
            ++i;
        }
        let cntj = 0;
        while (j < t.length && t[j] === ch) {
            ++cntj;
            ++j;
        }
        if (cnti < cntj) {
            return false;
        }
        if (cnti !== cntj && cnti < 3) {
            return false;
        }
    }
    return i === s.length && j === t.length;
};
[sol1-Golang]
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
func expand(s, t string) bool {
    n, m := len(s), len(t)
    i, j := 0, 0
    for i < n && j < m {
        if s[i] != t[j] {
            return false
        }
        ch := s[i]
        cntI := 0
        for i < n && s[i] == ch {
            cntI++
            i++
        }
        cntJ := 0
        for j < m && t[j] == ch {
            cntJ++
            j++
        }
        if cntI < cntJ || cntI > cntJ && cntI < 3 {
            return false
        }
    }
    return i == n && j == m
}

func expressiveWords(s string, words []string) (ans int) {
    for _, word := range words {
        if expand(s, word) {
            ans++
        }
    }
    return
}

复杂度分析

  • 时间复杂度：O(n|s| + \sum_i |\textit{words}_i|)，其中 n 是数组 words 的长度，|s| 和 words}_i 分别是字符串 s 和数组 words 中第 i 个字符串的长度。

  • 空间复杂度：O(1)。

 Comments
On this page
0809-情感丰富的文字