2559-统计范围内的元音字符串数

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    

给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。

每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内（ 包含
这两个值）并且以元音开头和结尾的字符串的数目。

返回一个整数数组，其中数组的第 i 个元素对应第 i 个查询的答案。

注意： 元音字母是 'a'、'e'、'i'、'o' 和 'u' 。

示例 1：

**输入：** words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
**输出：** [2,3,0]
**解释：** 以元音开头和结尾的字符串是 "aba"、"ece"、"aa" 和 "e" 。
查询 [0,2] 结果为 2（字符串 "aba" 和 "ece"）。
查询 [1,4] 结果为 3（字符串 "ece"、"aa"、"e"）。
查询 [1,1] 结果为 0 。
返回结果 [2,3,0] 。

示例 2：

**输入：** words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
**输出：** [3,2,1]
**解释：** 每个字符串都满足这一条件，所以返回 [3,2,1] 。

提示：

  • 1 <= words.length <= 105
  • 1 <= words[i].length <= 40
  • words[i] 仅由小写英文字母组成
  • sum(words[i].length) <= 3 * 105
  • 1 <= queries.length <= 105
  • 0 <= queries[j][0] <= queries[j][1] < words.length

方法一：前缀和

为方便表述，以下将以元音开头和结尾的字符串称为「元音字符串」。

这道题要求返回一系列查询的答案，每个查询为计算特定区间中的元音字符串数。可以使用前缀和实现区间查询。

用 n 表示数组 words 的长度，创建长度为 n + 1 的数组 prefixSums，其中 prefixSums}[i] 表示数组 words 的前 i 个字符串（即下标范围 [0, i - 1] 的字符串）中的元音字符串数，prefixSums}[0] = 0。

从左到右遍历数组 words，对于下标 0 \le i < n，执行如下操作：

  • 如果 words}[i] 是元音字符串，则 prefixSums}[i + 1] = \textit{prefixSums}[i] + 1；

  • 如果 words}[i] 不是元音字符串，则 prefixSums}[i + 1] = \textit{prefixSums}[i]。

得到前缀和数组之后，对于 0 \le i \le j < n，区间 [i, j] 中的元音字符串数是 prefixSums}[j + 1] - \textit{prefixSums}[i]。

用 ans}[i] 表示第 i 个查询 queries}[i] 的答案。如果 queries}[i] = [\textit{start}_i, \textit{end}_i]，则 ans}[i] = \textit{prefixSums}[\textit{end}_i + 1] - \textit{prefixSums}[\textit{start}_i]。

遍历所有的查询之后，即可得到答案数组 ans。

[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
class Solution {
    public int[] vowelStrings(String[] words, int[][] queries) {
        int n = words.length;
        int[] prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int value = isVowelString(words[i]) ? 1 : 0;
            prefixSums[i + 1] = prefixSums[i] + value;
        }
        int q = queries.length;
        int[] ans = new int[q];
        for (int i = 0; i < q; i++) {
            int start = queries[i][0], end = queries[i][1];
            ans[i] = prefixSums[end + 1] - prefixSums[start];
        }
        return ans;
    }

    public boolean isVowelString(String word) {
        return isVowelLetter(word.charAt(0)) && isVowelLetter(word.charAt(word.length() - 1));
    }

    public boolean isVowelLetter(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}
[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
public class Solution {
    public int[] VowelStrings(string[] words, int[][] queries) {
        int n = words.Length;
        int[] prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int value = IsVowelString(words[i]) ? 1 : 0;
            prefixSums[i + 1] = prefixSums[i] + value;
        }
        int q = queries.Length;
        int[] ans = new int[q];
        for (int i = 0; i < q; i++) {
            int start = queries[i][0], end = queries[i][1];
            ans[i] = prefixSums[end + 1] - prefixSums[start];
        }
        return ans;
    }

    public bool IsVowelString(string word) {
        return IsVowelLetter(word[0]) && IsVowelLetter(word[word.Length - 1]);
    }

    public bool IsVowelLetter(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}
[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
class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        int n = words.size();
        int prefixSums[n + 1];
        memset(prefixSums, 0, sizeof(prefixSums));
        for (int i = 0; i < n; i++) {
            int value = isVowelString(words[i]) ? 1 : 0;
            prefixSums[i + 1] = prefixSums[i] + value;
        }
        vector<int> ans(queries.size());
        for (int i = 0; i < queries.size(); i++) {
            int start = queries[i][0], end = queries[i][1];
            ans[i] = prefixSums[end + 1] - prefixSums[start];
        }
        return ans;
    }

    bool isVowelString(const string &word) {
        return isVowelLetter(word[0]) && isVowelLetter(word.back());
    }

    bool isVowelLetter(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
};

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        def isVowelString(word):
            return isVowelLetter(word[0]) and isVowelLetter(word[-1])

        def isVowelLetter(c):
            return c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'

        n = len(words)
        prefix_sums = [0] * (n + 1)
        for i in range(n):
            value = 1 if isVowelString(words[i]) else 0
            prefix_sums[i + 1] = prefix_sums[i] + value
        ans = []
        for i in range(len(queries)):
            start, end = queries[i]
            ans.append(prefix_sums[end + 1] - prefix_sums[start])
        return ans
[sol1-Go]
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
func vowelStrings(words []string, queries [][]int) []int {
    n := len(words)
    prefixSums := make([]int, n + 1)
    for i := 0; i < n; i++ {
        value := 0
        if isVowelString(words[i]) {
            value = 1
        }
        prefixSums[i + 1] = prefixSums[i] + value
    }
    ans := make([]int, len(queries))
    for i := 0; i < len(queries); i++ {
        start := queries[i][0]
        end := queries[i][1]
        ans[i] = prefixSums[end + 1] - prefixSums[start]
    }
    return ans
}

func isVowelString(word string) bool {
    return isVowelLetter(word[0]) && isVowelLetter(word[len(word) - 1])
}

func isVowelLetter(c byte) bool {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var vowelStrings = function(words, queries) {
    let n = words.length;
    let prefixSums = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        let value = isVowelString(words[i]) ? 1 : 0;
        prefixSums[i + 1] = prefixSums[i] + value;
    }
    let ans = [];
    for (let i = 0; i < queries.length; i++) {
        let start = queries[i][0], end = queries[i][1];
        ans.push(prefixSums[end + 1] - prefixSums[start]);
    }
    return ans;
}

function isVowelString(word) {
    return isVowelLetter(word[0]) && isVowelLetter(word[word.length - 1]);
}

function isVowelLetter(c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
[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
bool isVowelLetter(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

bool isVowelString(const char *word) {
    int len = strlen(word);
    return isVowelLetter(word[0]) && isVowelLetter(word[len - 1]);
}

int* vowelStrings(char ** words, int wordsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int n = wordsSize;
    int prefixSums[n + 1];
    memset(prefixSums, 0, sizeof(prefixSums));
    for (int i = 0; i < n; i++) {
        int value = isVowelString(words[i]) ? 1 : 0;
        prefixSums[i + 1] = prefixSums[i] + value;
    }
    int *ans = (int *)calloc(queriesSize, sizeof(int));
    for (int i = 0; i < queriesSize; i++) {
        int start = queries[i][0], end = queries[i][1];
        ans[i] = prefixSums[end + 1] - prefixSums[start];
    }
    *returnSize = queriesSize;
    return ans;
}

复杂度分析

  • 时间复杂度：O(n + q)，其中 n 是数组 words 的长度，q 是数组 queries 的长度（即查询数）。计算前缀和数组的时间是 O(n)，然后计算 q 个查询的答案，计算每个查询的答案的时间是 O(1)，因此时间复杂度是 O(n + q)。

  • 空间复杂度：O(n)，其中 n 是数组 words 的长度。需要创建长度为 n + 1 的前缀和数组。注意返回值不计入空间复杂度。

 Comments
On this page
2559-统计范围内的元音字符串数