【LetMeFly】2559.統(tǒng)計范圍內(nèi)的元音字符串數(shù)

力扣題目鏈接：https://leetcode.cn/problems/count-vowel-strings-in-ranges/

給你一個下標從 0 開始的字符串數(shù)組 words 以及一個二維整數(shù)數(shù)組 queries 。

每個查詢 queries[i] = [li, ri] 會要求我們統(tǒng)計在 words 中下標在 li 到 ri 范圍內(nèi)（包含 這兩個值）并且以元音開頭和結(jié)尾的字符串的數(shù)目。

返回一個整數(shù)數(shù)組，其中數(shù)組的第 i 個元素對應第 i 個查詢的答案。

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

?

示例 1：

輸入：words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
輸出：[2,3,0]
解釋：以元音開頭和結(jié)尾的字符串是 "aba"、"ece"、"aa" 和 "e" 。
查詢 [0,2] 結(jié)果為 2（字符串 "aba" 和 "ece"）。
查詢 [1,4] 結(jié)果為 3（字符串 "ece"、"aa"、"e"）。
查詢 [1,1] 結(jié)果為 0 。
返回結(jié)果 [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

方法一：前綴和

這道題說白了就是給出多次詢問，每次問你第l到第r個單詞中，有多少個單詞的首字母和尾字母都是元音字母。

暴力求解肯定會超時，因此這就需要使用一個技巧，叫“前綴和”。

假設(shè)words中有n個單詞，那么我們創(chuàng)建一個長度為n+1的數(shù)組prefix，prefix[0] = 0。

令$prefix[i+1]$代表words的下標0到i的單詞中首尾都是元音字母的單詞個數(shù)，

那么$prefix[r+1]?prefix[l]$就是words的l到r中首尾都是元音字母的單詞個數(shù)。

并且prefix[i + 1]可以由prefix[i]和words[i]很輕松地得到。

• 時間復雜度$O(len(words)+len(queries))$
• 空間復雜度$O(len(words))$

AC代碼

C++

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

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        vector<int> prefix(words.size() + 1, 0);
        for (int i = 0; i < words.size(); i++) {
            prefix[i + 1] = prefix[i] + (isYuan(words[i][0]) && isYuan(words[i].back()));  // 這里&&外必須加括號，不然會先執(zhí)行prefix[i] + isYuan(words[i][0])，再將結(jié)果于isYuan(words[i].back())做與運算
            // printf("prefix[%d] = %d, prefix[%d] = %d\n", i, prefix[i], i + 1, prefix[i + 1]);  //**********
        }
        // for (int t : prefix) {printf("%d ", t);} puts("");  //**********
        vector<int> ans(queries.size());
        for (int i = 0; i < queries.size(); i++) {
            ans[i] = prefix[queries[i][1] + 1] - prefix[queries[i][0]];
        }
        return ans;
    }
};

Python

# from typing import List

def isYuan(c: str) -> bool:
    return c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        prefix = [0] * (len(words) + 1)
        for i in range(len(words)):
            prefix[i + 1] = prefix[i] + (isYuan(words[i][0]) and isYuan(words[i][-1]))
        return [prefix[q[1] + 1] - prefix[q[0]] for q in queries]

同步發(fā)文于CSDN，原創(chuàng)不易，轉(zhuǎn)載請附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/131014779文章來源地址http://www.zghlxwxcb.cn/news/detail-469057.html

到了這里，關(guān)于LeetCode 2559. 統(tǒng)計范圍內(nèi)的元音字符串數(shù)：前綴和的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！