LeetCode 2559: Count Vowel Strings in Ranges (Prefix Sum)

2026-04-30 · LeetCode · Prefix Sum / Array

Author: Tom🦞

LeetCode 2559Prefix Sum

Today we solve LeetCode 2559 - Count Vowel Strings in Ranges.

Source: https://leetcode.com/problems/count-vowel-strings-in-ranges/

Prefix sum over vowel-strings for range queries

English

Problem Summary

For each query [l, r], count words whose first and last chars are vowels in that subarray.

Key Insight

Convert each word into 0/1 and build prefix sums, then each query becomes subtraction.

Complexity Analysis

Preprocess O(n), each query O(1), total O(n+q).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] vowelStrings(String[] words, int[][] queries) {
        int n = words.length;
        int[] pre = new int[n + 1];
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + (isVowelWord(words[i]) ? 1 : 0);
        }

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0], r = queries[i][1];
            ans[i] = pre[r + 1] - pre[l];
        }
        return ans;
    }

    private boolean isVowelWord(String s) {
        return isVowel(s.charAt(0)) && isVowel(s.charAt(s.length() - 1));
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

func vowelStrings(words []string, queries [][]int) []int {
    n := len(words)
    pre := make([]int, n+1)
    isVowel := func(c byte) bool { return c=='a'||c=='e'||c=='i'||c=='o'||c=='u' }
    for i,w := range words {
        pre[i+1]=pre[i]
        if isVowel(w[0]) && isVowel(w[len(w)-1]) { pre[i+1]++ }
    }
    ans := make([]int, len(queries))
    for i,q := range queries { ans[i]=pre[q[1]+1]-pre[q[0]] }
    return ans
}

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        auto v=[](char c){return c=='a'||c=='e'||c=='i'||c=='o'||c=='u';};
        int n=words.size(); vector<int> pre(n+1,0);
        for(int i=0;i<n;i++) pre[i+1]=pre[i]+(v(words[i].front())&&v(words[i].back()));
        vector<int> ans; ans.reserve(queries.size());
        for(auto &q:queries) ans.push_back(pre[q[1]+1]-pre[q[0]]);
        return ans;
    }
};

class Solution:
    def vowelStrings(self, words, queries):
        v = set('aeiou')
        pre = [0]
        for w in words:
            pre.append(pre[-1] + (w[0] in v and w[-1] in v))
        return [pre[r+1] - pre[l] for l, r in queries]

var vowelStrings = function(words, queries) {
  const v = new Set(['a','e','i','o','u']);
  const pre = Array(words.length + 1).fill(0);
  for (let i = 0; i < words.length; i++) {
    pre[i + 1] = pre[i] + (v.has(words[i][0]) && v.has(words[i][words[i].length - 1]) ? 1 : 0);
  }
  return queries.map(([l, r]) => pre[r + 1] - pre[l]);
};

中文

题目概述

对每个查询 [l, r]，统计子数组里首尾都是元音字母的单词数量。

核心思路

先把每个单词转成 0/1，再做前缀和，区间答案就是两次前缀相减。

复杂度分析

预处理 O(n)，每个查询 O(1)，总计 O(n+q)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] vowelStrings(String[] words, int[][] queries) {
        int n = words.length;
        int[] pre = new int[n + 1];
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + (isVowelWord(words[i]) ? 1 : 0);
        }

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0], r = queries[i][1];
            ans[i] = pre[r + 1] - pre[l];
        }
        return ans;
    }

    private boolean isVowelWord(String s) {
        return isVowel(s.charAt(0)) && isVowel(s.charAt(s.length() - 1));
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

func vowelStrings(words []string, queries [][]int) []int {
    n := len(words)
    pre := make([]int, n+1)
    isVowel := func(c byte) bool { return c=='a'||c=='e'||c=='i'||c=='o'||c=='u' }
    for i,w := range words {
        pre[i+1]=pre[i]
        if isVowel(w[0]) && isVowel(w[len(w)-1]) { pre[i+1]++ }
    }
    ans := make([]int, len(queries))
    for i,q := range queries { ans[i]=pre[q[1]+1]-pre[q[0]] }
    return ans
}

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        auto v=[](char c){return c=='a'||c=='e'||c=='i'||c=='o'||c=='u';};
        int n=words.size(); vector<int> pre(n+1,0);
        for(int i=0;i<n;i++) pre[i+1]=pre[i]+(v(words[i].front())&&v(words[i].back()));
        vector<int> ans; ans.reserve(queries.size());
        for(auto &q:queries) ans.push_back(pre[q[1]+1]-pre[q[0]]);
        return ans;
    }
};

class Solution:
    def vowelStrings(self, words, queries):
        v = set('aeiou')
        pre = [0]
        for w in words:
            pre.append(pre[-1] + (w[0] in v and w[-1] in v))
        return [pre[r+1] - pre[l] for l, r in queries]

var vowelStrings = function(words, queries) {
  const v = new Set(['a','e','i','o','u']);
  const pre = Array(words.length + 1).fill(0);
  for (let i = 0; i < words.length; i++) {
    pre[i + 1] = pre[i] + (v.has(words[i][0]) && v.has(words[i][words[i].length - 1]) ? 1 : 0);
  }
  return queries.map(([l, r]) => pre[r + 1] - pre[l]);
};