Welcome to Subscribe On Youtube
3926. Count Valid Word Occurrences
Description
You are given an array of strings chunks. Concatenate all strings in chunks in order to form a string s.
You are also given an array of strings queries.
A joiner hyphen is a hyphen character '-' in s whose previous and next characters both exist and are lowercase English letters.
A word is a maximal substring of s consisting only of lowercase English letters and joiner hyphens.
All other characters, including spaces and hyphens that are not joiner hyphens, are treated as separators.
Return an integer array ans, where ans[i] is the number of times queries[i] appears as a word in s.
Example 1:
Input: chunks = ["hello wor","ld hello"], queries = ["hello","world","wor"]
Output: [2,1,0]
Explanation:
- After concatenating all strings in
chunks,s = "hello world hello". - The words are
"hello","world", and"hello". - The substring
"wor"appears inside"world", but it is not a full word.
Example 2:
Input: chunks = ["a-b a--b ","a-","b"], queries = ["a-b","a","b"]
Output: [2,1,1]
Explanation:
- After concatenating all strings in
chunks,s = "a-b a--b a-b". - In
"a-b", the hyphen is a joiner hyphen because it is between two lowercase English letters, so"a-b"is one word. - In
"a--b", neither hyphen is a joiner hyphen, so it is split into the words"a"and"b". - Therefore, the words are
"a-b","a","b", and"a-b".
Example 3:
Input: chunks = ["-cat dog- mouse"], queries = ["cat","dog","mouse","cat-dog"]
Output: [1,1,1,0]
Explanation:
- After concatenating all strings in
chunks,s = "-cat dog- mouse". - The leading hyphen before
"cat"and the trailing hyphen after"dog"are not joiner hyphens, so they are separators. - The words are
"cat","dog", and"mouse".
Constraints:
1 <= chunks.length <= 1051 <= chunks[i].length <= 105- The total length of all strings in
chunksdoes not exceed105. chunks[i]consists only of lowercase English letters, spaces, and'-'.1 <= queries.length <= 1051 <= queries[i].length <= 105- The total length of all strings in
queriesdoes not exceed105. queries[i]consists only of lowercase English letters and'-'.queries[i]is a valid word: it does not start or end with'-', and it does not contain two consecutive hyphens.
Solutions
Solution 1: Counting
First, we concatenate all strings in $\textit{chunks}$ to obtain a single string $s$.
Since the first character of a valid word must be a lowercase English letter, we scan $s$ from left to right. When we encounter a lowercase English letter, we continue scanning to the right. If we encounter a space or an invalid hyphen, it means we have found a word. We add this word to a hash table and count its occurrences. Finally, we iterate through each string in $\textit{queries}$, look up its count in the hash table, and append the result to the answer array.
The time complexity is $O(n + m)$, where $n$ is the total length of all strings in $\textit{chunks}$, and $m$ is the total length of all strings in $\textit{queries}$.
-
class Solution { public int[] countWordOccurrences(String[] chunks, String[] queries) { StringBuilder sb = new StringBuilder(); for (String chunk : chunks) { sb.append(chunk); } String s = sb.toString(); int n = s.length(); Map<String, Integer> cnt = new HashMap<>(); int i = 0; while (i < n) { char c = s.charAt(i); if (c == ' ' || c == '-') { i++; continue; } int j = i; while (j < n) { char cj = s.charAt(j); if (cj == ' ') { break; } if (cj == '-') { if (j + 1 < n) { char cnext = s.charAt(j + 1); if (cnext == ' ' || cnext == '-') { break; } } else { break; } } j++; } String word = s.substring(i, j); cnt.put(word, cnt.getOrDefault(word, 0) + 1); i = j; } int[] ans = new int[queries.length]; for (int k = 0; k < queries.length; k++) { ans[k] = cnt.getOrDefault(queries[k], 0); } return ans; } } -
class Solution { public: vector<int> countWordOccurrences(vector<string>& chunks, vector<string>& queries) { string s = ""; for (const string& chunk : chunks) { s += chunk; } int n = s.length(); unordered_map<string, int> cnt; int i = 0; while (i < n) { if (s[i] == ' ' || s[i] == '-') { i++; continue; } int j = i; while (j < n && s[j] != ' ' && (s[j] != '-' || (j + 1 < n && s[j + 1] != ' ' && s[j + 1] != '-'))) { j++; } cnt[s.substr(i, j - i)]++; i = j; } vector<int> ans; ans.reserve(queries.size()); for (const string& q : queries) { ans.push_back(cnt[q]); } return ans; } }; -
class Solution: def countWordOccurrences(self, chunks: list[str], queries: list[str]) -> list[int]: s = "".join(chunks) n = len(s) cnt = defaultdict(int) i = 0 while i < n: if s[i] in " -": i += 1 continue j = i while ( j < n and s[j] != " " and (s[j] != "-" or (j + 1 < n and s[j + 1] not in " -")) ): j += 1 cnt[s[i:j]] += 1 i = j return [cnt[q] for q in queries] -
func countWordOccurrences(chunks []string, queries []string) []int { s := strings.Join(chunks, "") n := len(s) cnt := make(map[string]int) i := 0 for i < n { if s[i] == ' ' || s[i] == '-' { i++ continue } j := i for j < n && s[j] != ' ' && (s[j] != '-' || (j+1 < n && s[j+1] != ' ' && s[j+1] != '-')) { j++ } cnt[s[i:j]]++ i = j } ans := make([]int, len(queries)) for k, q := range queries { ans[k] = cnt[q] } return ans } -
function countWordOccurrences(chunks: string[], queries: string[]): number[] { const s = chunks.join(''); const n = s.length; const cnt = new Map<string, number>(); let i = 0; while (i < n) { if (s[i] === ' ' || s[i] === '-') { i++; continue; } let j = i; while ( j < n && s[j] !== ' ' && (s[j] !== '-' || (j + 1 < n && s[j + 1] !== ' ' && s[j + 1] !== '-')) ) { j++; } const word = s.substring(i, j); cnt.set(word, (cnt.get(word) || 0) + 1); i = j; } return queries.map(q => cnt.get(q) || 0); }