Posts tagged as “vowel”

花花酱 LeetCode 2586. Count the Number of Vowel Strings in Range

By zxi on March 11, 2023

You are given a 0-indexed array of string words and two integers left and right.

A string is called a vowel string if it starts with a vowel character and ends with a vowel character where vowel characters are 'a', 'e', 'i', 'o', and 'u'.

Return the number of vowel strings words[i] where i belongs to the inclusive range [left, right].

Example 1:

Input: words = ["are","amy","u"], left = 0, right = 2
Output: 2
Explanation: 
- "are" is a vowel string because it starts with 'a' and ends with 'e'.
- "amy" is not a vowel string because it does not end with a vowel.
- "u" is a vowel string because it starts with 'u' and ends with 'u'.
The number of vowel strings in the mentioned range is 2.

Example 2:

Input: words = ["hey","aeo","mu","ooo","artro"], left = 1, right = 4
Output: 3
Explanation: 
- "aeo" is a vowel string because it starts with 'a' and ends with 'o'.
- "mu" is not a vowel string because it does not start with a vowel.
- "ooo" is a vowel string because it starts with 'o' and ends with 'o'.
- "artro" is a vowel string because it starts with 'a' and ends with 'o'.
The number of vowel strings in the mentioned range is 3.

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 10
words[i] consists of only lowercase English letters.
0 <= left <= right < words.length

Solution:

Iterator overs words, from left to right. Check the first and last element of the string.

Time complexity: O(|right – left + 1|)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int vowelStrings(vector<string>& words, int left, int right) {

auto isVowel = [](char c) {

return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';

};

return count_if(begin(words) + left, begin(words) + right + 1, [&](const string& w) {

return isVowel(w.front()) && isVowel(w.back());

});

}

};

花花酱 LeetCode 2559. Count Vowel Strings in Ranges

By zxi on February 4, 2023

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 l_i to r_i (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 i^th 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].

Constraints:

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

Solution: Prefix Sum

Let sum[i] := number of valid strings in words[0:i]

For each query [l, r], answer will be sum[r + 1] – sum[l]

Time complexity: O(n + q)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {

const size_t n = words.size();

vector<int> sum(n + 1);

auto check = [](char c) {

return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';

};

for (size_t i = 0; i < n; ++i)

sum[i + 1] = sum[i] +

(check(words[i][0]) && check(words[i][words[i].size() - 1]));

vector<int> ans;

for (const auto& q : queries)

ans.push_back(sum[q[1] + 1] - sum[q[0]]);

return ans;

}

};

花花酱 LeetCode 1704. Determine if String Halves Are Alike

By zxi on December 27, 2020

You are given a string s of even length. Split this string into two halves of equal lengths, and let a be the first half and b be the second half.

Two strings are alike if they have the same number of vowels ('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'). Notice that s contains uppercase and lowercase letters.

Return true if a and b are alike. Otherwise, return false.

Example 1:

Input: s = "book"
Output: true
Explanation: a = "bo" and b = "ok". a has 1 vowel and b has 1 vowel. Therefore, they are alike.

Example 2:

Input: s = "textbook"
Output: false
Explanation: a = "text" and b = "book". a has 1 vowel whereas b has 2. Therefore, they are not alike.
Notice that the vowel o is counted twice.

Example 3:

Input: s = "MerryChristmas"
Output: false

Example 4:

Input: s = "AbCdEfGh"
Output: true

Constraints:

2 <= s.length <= 1000
s.length is even.
s consists of uppercase and lowercase letters.

Solution: Counting

Time complexity: O(n)
Space complexity: O(1)

Python3

# Author: Huahua

class Solution:

def halvesAreAlike(self, s: str) -> bool:

def count(s: str) -> int:

return sum(c in 'aeiouAEIOU' for c in s)

n = len(s)

return count(s[:n//2]) == count(s[n//2:])

花花酱 LeetCode 966. Vowel Spellchecker

By zxi on December 30, 2018

Problem

Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word.

For a given query word, the spell checker handles two categories of spelling mistakes:

Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.
- Example: wordlist = ["yellow"], query = "YellOw": correct = "yellow"
- Example: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
- Example: wordlist = ["yellow"], query = "yellow": correct = "yellow"
Vowel Errors: If after replacing the vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.
- Example: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
- Example: wordlist = ["YellOw"], query = "yeellow": correct = "" (no match)
- Example: wordlist = ["YellOw"], query = "yllw": correct = "" (no match)

In addition, the spell checker operates under the following precedence rules:

When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
When the query matches a word up to capitlization, you should return the first such match in the wordlist.
When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
If the query has no matches in the wordlist, you should return the empty string.

Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].

Example 1:

Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

Note:

1 <= wordlist.length <= 5000
1 <= queries.length <= 5000
1 <= wordlist[i].length <= 7
1 <= queries[i].length <= 7
All strings in wordlist and queries consist only of english letters.

Solution: HashTable

Using 3 hashtables: original words, lower cases, lower cases with vowels replaced to “*”

Time complexity: O(|W|+|Q|)
Space complexity: O(|W|)

C++

class Solution {

public:

vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {

vector<string> ans;

unordered_map<string, string> m_org;

unordered_map<string, string> m_low;

unordered_map<string, string> m_vow;

for (const string& w : wordlist) {

// Original word

m_org[w] = w;

// Case-insensitive

string l = toLower(w);

if (!m_low.count(l)) m_low[l] = w;

// Vowel-insensitive

string o = replaceVowels(l);

if (!m_vow.count(o)) m_vow[o] = w;

}

for (const string& q : queries) {

if (m_org.count(q)) {

ans.push_back(q);

continue;

}

string l = toLower(q);

if (m_low.count(l)) {

ans.push_back(m_low[l]);

continue;

}

string o = replaceVowels(l);

if (m_vow.count(o)) {

ans.push_back(m_vow[o]);

continue;

}

ans.push_back("");

}

return ans;

}

private:

string toLower(const string& s) {

string l(s);

std::transform(begin(s), end(s), begin(l), ::tolower);

return l;

}

string replaceVowels(const string& s) {

string o(s);

for (char& c : o)

if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')

c = '*';

return o;

}

};

Python3

class Solution:

def spellchecker(self, wordlist, queries):

org = dict()

low = dict()

vow = dict()

for w in wordlist:

org[w] = w

l = w.lower()

if l not in low: low[l] = w

v = re.sub(r'[aeiou]', '*', l)

if v not in vow: vow[v] = w

ans = []

for q in queries:

if q in org:

ans.append(q)

continue

l = q.lower()

if l in low:

ans.append(low[l])

continue

v = re.sub(r'[aeiou]', '*', l)

if v in vow:

ans.append(vow[v])

continue

ans.append("")

return ans