[LeetCode] 2559. Count Vowel Strings in Ranges (Python)

 

난이도: Medium

 

문제 설명

---

You are given a 0-indexed array of strings words and a 2D array of integers queries.

 

Each query queries[i] = [l_i, r_i] asks us to find the number of strings present in the range li to ri (both inclusive) of words that start and end with a vowel.

 

Return an array ans of size queries.length, where ans[i] is the answer to the ith query.

 

Note that the vowel letters are 'a', 'e', 'i', 'o', and 'u'.

 

문제 예제

---

Example 1:

Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
Output: [2,3,0]
Explanation: The strings starting and ending with a vowel are "aba", "ece", "aa" and "e".
The answer to the query [0,2] is 2 (strings "aba" and "ece").
to query [1,4] is 3 (strings "ece", "aa", "e").
to query [1,1] is 0.
We return [2,3,0].

Example 2:

Input: words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
Output: [3,2,1]
Explanation: Every string satisfies the conditions, so we return [3,2,1].

 

제한 사항

---

• 1 <= words.length <= 10^5
• 1 <= words[i].length <= 40
• words[i] consists only of lowercase English letters.
• sum(words[i].length) <= 3 * 10^5
• 1 <= queries.length <= 10^5
• 0 <= l_i <= r_i < words.length

 

✏️ Solution(솔루션)

---

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        n = len(words)
        prefix = [0 for _ in range(n)]
        vowels = ['a', 'e', 'i', 'o', 'u']
        answer = []

        if words[0][0] in vowels and words[0][-1] in vowels:
            prefix[0] = 1

        for i in range(1, n):
            if words[i][0] in vowels and words[i][-1] in vowels:
                prefix[i] = prefix[i-1] + 1
            else:
                prefix[i] = prefix[i-1]

        for query in queries:
            if query[0] == 0:
                answer.append(prefix[query[1]])
            else:
                answer.append(prefix[query[1]] - prefix[query[0]-1])
        
        return answer

 

 

prefix sum을 사용하면 쉽게 풀 수 있는 문제인 것 같다.

 

먼저, words 리스트에서 0번 인덱스부터 i번 인덱스까지 조건을 만족하는 문자열의 누적 개수를 저장하는 prefix라는 리스트를 만들었다.

 

그리고 각 query마다 query[0]이 0이라고 한다면 그냥 prefix[query[1]]을 answer라는 리스트에 넣었고,

query[0]이 0이 아니라고 한다면 prefix[query[1]] - prefix[query[0]-1] 값을 answer에 넣었다.

이렇게 하면 query 부분의 조건을 만족하는 word의 갯수를 구할 수 있다.

 

마지막으로 answer를 return하고 정답을 맞출 수 있었다.

---

문제: 2559. Count Vowel Strings in Ranges

깃허브: github

algorithm_practice/LeetCode/2691-count-vowel-strings-in-ranges at main · laewonJeong/algorithm_practice