Given a string A and a vector of strings B, the task is to count the number of strings in vector B that only contains the words from A.
Examples:
Input: A=”blue green red yellow”
B[]={“blue red”, “green pink”, “yellow green”}
Output: 2Input: A=”apple banana pear”
B[]={“apple”, “banana apple”, “pear banana”}
Output: 3
Approach: Follow the below steps to solve this problem:
- Extract all the words of string A and store them in a set, say st.
- Now traverse on each string in vector B, and get all the words in that string.
- Now check that if all words are present in st, then increment ans by 1.
- Return ans as the solution to the problem.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to extract all words from a stringvector<string> getWords(string A){ vector<string> words; string t; for (int i = 0; i < A.size(); i++) { // If the character is a space if (A[i] == ' ') { if (t.size() > 0) { words.push_back(t); } t = ""; } // Else else { t += A[i]; } } // Last word if (t.size() > 0) { words.push_back(t); } return words;}// Function to count the number of strings in B// that only contains the words from Aint countStrings(string A, vector<string>& B){ unordered_set<string> st; vector<string> words; words = getWords(A); for (auto x : words) { st.insert(x); } // Variable to store the final answer int ans = 0; for (auto x : B) { words = getWords(x); bool flag = 0; for (auto y : words) { if (st.find(y) == st.end()) { flag = 1; break; } } // If all the words are in set st if (!flag) { ans++; } } return ans;}// Driver Codeint main(){ string A = "blue green red yellow"; vector<string> B = { "blue red", "green pink", "yellow green" }; cout << countStrings(A, B);} |
Java
// Java code for the above approachimport java.util.*;class GFG{ // Function to extract all words from a String static Vector<String> getWords(String A) { Vector<String> words = new Vector<String>(); String t=""; for (int i = 0; i < A.length(); i++) { // If the character is a space if (A.charAt(i) == ' ') { if (t.length() > 0) { words.add(t); } t = ""; } // Else else { t += A.charAt(i); } } // Last word if (t.length() > 0) { words.add(t); } return words; } // Function to count the number of Strings in B // that only contains the words from A static int countStrings(String A, String[] B) { HashSet<String> st = new HashSet<>(); Vector<String> words = new Vector<String>(); words = getWords(A); for (String x : words) { st.add(x); } // Variable to store the final answer int ans = 0; for (String x : B) { words = getWords(x); boolean flag = false; for (String y : words) { if (!st.contains(y)) { flag = true; break; } } // If all the words are in set st if (!flag) { ans++; } } return ans; } // Driver Code public static void main(String[] args) { String A = "blue green red yellow"; String []B = { "blue red", "green pink", "yellow green" }; System.out.print(countStrings(A, B)); }}// This code is contributed by 29AjayKumar |
Python3
# Python 3 code for the above approach# Function to extract all words from a stringdef getWords(A): words = [] t = "" for i in range(len(A)): # If the character is a space if (A[i] == ' '): if (len(t) > 0): words.append(t) t = "" # Else else: t += A[i] # Last word if (len(t) > 0): words.append(t) return words# Function to count the number of strings in B# that only contains the words from Adef countStrings(A, B): st = set([]) words = [] words = getWords(A) for x in words: st.add(x) # Variable to store the final answer ans = 0 for x in B: words = getWords(x) flag = 0 for y in words: if (y not in st): flag = 1 break # If all the words are in set st if (not flag): ans += 1 return ans# Driver Codeif __name__ == "__main__": A = "blue green red yellow" B = ["blue red", "green pink", "yellow green"] print(countStrings(A, B)) # This code is contributed by ukasp. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to extract all words from a String static List<String> getWords(String A) { List<String> words = new List<String>(); String t=""; for (int i = 0; i < A.Length; i++) { // If the character is a space if (A[i] == ' ') { if (t.Length > 0) { words.Add(t); } t = ""; } // Else else { t += A[i]; } } // Last word if (t.Length > 0) { words.Add(t); } return words; } // Function to count the number of Strings in B // that only contains the words from A static int countStrings(String A, String[] B) { HashSet<String> st = new HashSet<String>(); List<String> words = new List<String>(); words = getWords(A); foreach (String x in words) { st.Add(x); } // Variable to store the readonly answer int ans = 0; foreach (String x in B) { words = getWords(x); bool flag = false; foreach (String y in words) { if (!st.Contains(y)) { flag = true; break; } } // If all the words are in set st if (!flag) { ans++; } } return ans; } // Driver Code public static void Main(String[] args) { String A = "blue green red yellow"; String []B = { "blue red", "green pink", "yellow green" }; Console.Write(countStrings(A, B)); }}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code for the above approach // Function to extract all words from a string function getWords(A) { let words = []; let t; for (let i = 0; i < A.length; i++) { // If the character is a space if (A[i] == ' ') { if (t.length > 0) { words.push(t); } t = ""; } // Else else { t += A[i]; } } // Last word if (t.length > 0) { words.push(t); } return words; } // Function to count the number of strings in B // that only contains the words from A function countStrings(A, B) { let st = new Set(); let words; words = getWords(A); for (let x of words) { st.add(x); } // Variable to store the final answer let ans = 0; for (let x of B) { words = getWords(x); let flag = 0; for (let y = 0; y < words.length; y++) { if (st.has(words[y])) { flag = 1; break; } } // If all the words are in set st if (flag == 0) { ans++; } } return ans + 1; } // Driver Code let A = "blue green red yellow"; let B = ["blue red", "green pink", "yellow green"]; document.write(countStrings(A, B));// This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(N*M), where N is the size of vector B and M is the maximum length of in B.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
