Given n sentences. The task is to count the number of words that appear in all of these sentences.
Note that every word consists of only lowercase English alphabets.
Examples:
Input: arr[] = {
“there is a cow”,
“cow is our mother”,
“cow gives us milk and milk is sweet”,
“there is a boy who loves cow”}
Output: 2
Only the words “is” and “cow” appear in all of the sentences.Input: arr[] = {
“abc aac abcd ccc”,
“ac aa abc cca”,
“abca aaac abcd ccc”}
Output: 0
Naive Approach: The naive approach is to take every word of the first sentence and compare it with the rest of the lines if it is also present in all lines then increment the count.
- Iterate over every word of the first sentence.
- Check if the current word exists in all the rest sentences.
- If exist, increment the count by 1.
- Check if the current word exists in all the rest sentences.
- Finally, return the value of the count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to check if word s1 is present in sentence s2 or// not.bool isContain(string& s1, string& s2){ stringstream ss(s2); string word; while (ss >> word) { if (word == s1) return true; } return false;}// Function to return the count of common words// in all the sentencesint commonWords(vector<string>& S){ int count = 0; stringstream ss(S[0]); string word; // Iterate over every word of first sentence. while (ss >> word) { bool flag = true; // Check if the current word exist in all the rest // sentences. for (int j = 1; j < S.size(); j++) { if (isContain(word, S[j]) == false) { flag = false; break; } } // If exist, the increment the count by 1. if (flag) count++; } // Finally return the value of count. return count;}// Driver codeint main(){ vector<string> S; S.push_back("there is a cow"); S.push_back("cow is our mother"); S.push_back("cow gives us milk and milk is sweet"); S.push_back("there is a boy who loves cow"); cout << commonWords(S); return 0;} |
Java
// Function to check if word s1 is present in sentence s2 or// not.import java.util.*;import java.io.*;public class GFG { public static boolean isContain(String s1, String s2) { StringTokenizer st = new StringTokenizer(s2); String word; while (st.hasMoreTokens()) { word = st.nextToken(); if (word.equals(s1)) return true; } return false; } // Function to return the count of common words // in all the sentences public static int commonWords(Vector<String> S) { int count = 0; StringTokenizer st = new StringTokenizer(S.get(0)); String word; // Iterate over every word of first sentence. while (st.hasMoreTokens()) { boolean flag = true; word = st.nextToken(); // Check if the current word exist in all the // rest sentences. for (int j = 1; j < S.size(); j++) { if (isContain(word, S.get(j)) == false) { flag = false; break; } } // If exist, the increment the count by 1. if (flag) count++; } // Finally return the value of count. return count; } // Driver code public static void main(String[] args) { Vector<String> S = new Vector<String>(); S.add("there is a cow"); S.add("cow is our mother"); S.add("cow gives us milk and milk is sweet"); S.add("there is a boy who loves cow"); System.out.println(commonWords(S)); }} |
Python3
def isContain(s1, s2): s2 = s2.split() return s1 in s2def commonWords(S): count = 0 words = S[0].split() for word in words: flag = True for i in range(1, len(S)): if not isContain(word, S[i]): flag = False break if flag: count += 1 return countS = ["there is a cow", "cow is our mother", "cow gives us milk and milk is sweet", "there is a boy who loves cow"]print(commonWords(S)) |
Javascript
function isContain(s1, s2) { let words = s2.split(" "); return words.includes(s1);}function commonWords(S) { let count = 0; let words = S[0].split(" "); for (let i = 0; i < words.length; i++) { let flag = true; for (let j = 1; j < S.length; j++) { if (!isContain(words[i], S[j])) { flag = false; break; } } if (flag) { count += 1; } } return count;}let S = ["there is a cow", "cow is our mother", "cow gives us milk and milk is sweet", "there is a boy who loves cow"];console.log(commonWords(S));// This code is contributed by uomkar369 |
C#
using System;using System.Collections.Generic;using System.Linq;class Gfg { // Function to check if word s1 is present in sentence // s2 or not. static bool IsContain(string s1, string s2) { var words = s2.Split(' '); return words.Contains(s1); } // Function to return the count of common words // in all the sentences static int CommonWords(List<string> S) { int count = 0; var words = S[0].Split(' '); // Iterate over every word of first sentence. foreach(var word in words) { bool flag = true; // Check if the current word exist in all the // rest sentences. for (int j = 1; j < S.Count; j++) { if (!IsContain(word, S[j])) { flag = false; break; } } // If exist, the increment the count by 1. if (flag) count++; } // Finally return the value of count. return count; } static void Main(string[] args) { var S = new List<string>() { "there is a cow", "cow is our mother", "cow gives us milk and milk is sweet", "there is a boy who loves cow" }; Console.WriteLine(CommonWords(S)); }}// This code is contributed by divya_p123. |
Output
2
Time Complexity: O(N2), where N is the total words present in all sentences.
Auxiliary Space: O(1)
Efficient Approach: For all the words of the first sentence, we can check if it is also present in all the other sentences in constant time by using a map. Store all the words of the first sentence in a map and check how many of these stored words are present in all the other sentences.
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count of common words// in all the sentencesint commonWords(vector<string> S){ int m, n, i, j; // To store separate words string str; // It will be used to check if a word is present // in a particular string unordered_map<string, bool> has; // To store all the words of first string vector<pair<string, bool> > ans; pair<string, bool> tmp; // m will store number of strings in given vector m = S.size(); i = 0; // Extract all words of first string and store it in ans while (i < S[0].size()) { str = ""; while (i < S[0].size() && S[0][i] != ' ') { str += S[0][i]; i++; } // Increase i to get at starting index // of the next word i++; // If str is not empty store it in map if (str != "") { tmp = make_pair(str, true); ans.push_back(tmp); } } // Start from 2nd line check if any word of // the first string did not match with // some word in the current line for (j = 1; j < m; j++) { has.clear(); i = 0; while (i < S[j].size()) { str = ""; while (i < S[j].size() && S[j][i] != ' ') { str += S[j][i]; i++; } i++; if (str != "") { has[str] = true; } } // Check all words of this vector // if it is not present in current line // make it false for (int k = 0; k < ans.size(); k++) { if (ans[k].second != false && has[ans[k].first] == false) { ans[k].second = false; } // This line is used to consider only distinct words else if (ans[k].second != false && has[ans[k].first] == true) { has[ans[k].first] = false; } } } // This function will print // the count of common words int cnt = 0; // If current word appears in all the sentences for (int k = 0; k < ans.size(); k++) { if (ans[k].second == true) cnt++; } return cnt;}// Driver codeint main(){ vector<string> S; S.push_back("there is a cow"); S.push_back("cow is our mother"); S.push_back("cow gives us milk and milk is sweet"); S.push_back("there is a boy who loves cow"); cout << commonWords(S); return 0;} |
Java
// Java implementation of the approach import java.util.HashMap;class GFG{ // Function to return the count of // common words in all the sentences static int commonWords(String[] s) { int m, i, j; // To store separate words String str; // It will be used to check if a word // is present in a particular string HashMap<String, Boolean> has = new HashMap<>(); // To store all the words of first string String[] ans1 = new String[100]; boolean[] ans2 = new boolean[100]; int track = 0; // m will store number of strings // in given vector m = s.length; i = 0; // Extract all words of first string // and store it in ans while (i < s[0].length()) { str = ""; while (i < s[0].length() && s[0].charAt(i) != ' ') { str += s[0].charAt(i); i++; } // Increase i to get at starting index // of the next word i++; // If str is not empty store it in map if (str.compareTo("") != 0) { ans1[track] = str; ans2[track] = true; track++; } } // Start from 2nd line check if any word of // the first string did not match with // some word in the current line for (j = 1; j < m; j++) { has.clear(); i = 0; while (i < s[j].length()) { str = ""; while (i < s[j].length() && s[j].charAt(i) != ' ') { str += s[j].charAt(i); i++; } i++; if (str.compareTo("") != 0) has.put(str, true); } // Check all words of this vector // if it is not present in current line // make it false for (int k = 0; k < track; k++) { // System.out.println(has.get(ans1[k])); if (ans2[k] != false && !has.containsKey(ans1[k])) ans2[k] = false; // This line is used to consider // only distinct words else if (ans2[k] != false && has.containsKey(ans1[k]) && has.get(ans1[k]) == true) has.put(ans1[k], false); } } // This function will print // the count of common words int cnt = 0; // If current word appears // in all the sentences for (int k = 0; k < track; k++) if (ans2[k] == true) cnt++; return cnt; } // Driver Code public static void main(String[] args) { String[] s = { "there is a cow", "cow is our mother", "cow gives us milk and milk is sweet", "there is a boy who loves cow" }; System.out.println(commonWords(s)); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 implementation of the approach from collections import defaultdict# Function to return the count of # common words in all the sentences def commonWords(S): # It will be used to check if a word # is present in a particular string has = defaultdict(lambda:False) # To store all the words of first string ans = [] # m will store number of strings # in given vector m = len(S) i = 0 # Extract all words of first string # and store it in ans while i < len(S[0]): string = "" while i < len(S[0]) and S[0][i] != ' ': string += S[0][i] i += 1 # Increase i to get at starting # index of the next word i += 1 # If str is not empty store it in map if string != "": ans.append([string, True]) # Start from 2nd line check if any word # of the first string did not match with # some word in the current line for j in range(1, m): has.clear() i = 0 while i < len(S[j]): string = "" while i < len(S[j]) and S[j][i] != ' ': string += S[j][i] i += 1 i += 1 if string != "": has[string] = True # Check all words of this vector # if it is not present in current # line make it false for k in range(0, len(ans)): if (ans[k][1] != False and has[ans[k][0]] == False): ans[k][1] = False # This line is used to consider # only distinct words elif (ans[k][1] != False and has[ans[k][0]] == True): has[ans[k][0]] = False # This function will print # the count of common words cnt = 0 # If current word appears in all # the sentences for k in range(0, len(ans)): if ans[k][1] == True: cnt += 1 return cnt # Driver code if __name__ == "__main__": S = [] S.append("there is a cow") S.append("cow is our mother") S.append("cow gives us milk and milk is sweet") S.append("there is a boy who loves cow") print(commonWords(S)) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the // above approach using System;using System.Collections.Generic;class GFG{// Function to return the count of // common words in all the sentencesstatic int commonWords(String[] s) { int m, i, j; // To store separate words String str; // It will be used to check // if a word is present in a // particular string Dictionary<String, Boolean> has = new Dictionary<String, Boolean>(); // To store all the words of // first string String[] ans1 = new String[100]; bool[] ans2 = new bool[100]; int track = 0; // m will store number of // strings in given vector m = s.Length; i = 0; // Extract all words of // first string and store // it in ans while (i < s[0].Length) { str = ""; while (i < s[0].Length && s[0][i] != ' ') { str += s[0][i]; i++; } // Increase i to get at // starting index of the // next word i++; // If str is not empty store // it in map if (str.CompareTo("") != 0) { ans1[track] = str; ans2[track] = true; track++; } } // Start from 2nd line check if // any word of the first string // did not match with some word // in the current line for (j = 1; j < m; j++) { has.Clear(); i = 0; while (i < s[j].Length) { str = ""; while (i < s[j].Length && s[j][i] != ' ') { str += s[j][i]; i++; } i++; if (str.CompareTo("") != 0) has[str] = true; } // Check all words of this // vector if it is not present // in current line make it false for (int k = 0; k < track; k++) { // Console.WriteLine(has[ans1[k])); if (ans2[k] != false && !has.ContainsKey(ans1[k])) ans2[k] = false; // This line is used to consider // only distinct words else if (ans2[k] != false && has.ContainsKey(ans1[k]) && has[ans1[k]] == true) has[ans1[k]] = false; } } // This function will print // the count of common words int cnt = 0; // If current word appears // in all the sentences for (int k = 0; k < track; k++) if (ans2[k] == true) cnt++; return cnt;}// Driver Codepublic static void Main(String[] args) { String[] s = {"there is a cow", "cow is our mother", "cow gives us milk" + "and milk is sweet", "there is a boy who" + "loves cow" }; Console.WriteLine(commonWords(s));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript implementation of the approach // Function to return the count of // common words in all the sentences function commonWords( s) { var m, i, j; // To store separate words var str; // It will be used to check if a word // is present in a particular string var has = new Map(); // To store all the words of first string var ans1 = []; var ans2 = []; var track = 0; // m will store number of strings // in given vector m = s.length; i = 0; // Extract all words of first string // and store it in ans while (i < s[0].length) { str = ""; while (i < s[0].length && s[0].charAt(i) != ' ') { str += s[0].charAt(i); i++; } // Increase i to get at starting index // of the next word i++; // If str is not empty store it in map if (str !== "") { ans1[track] = str; ans2[track] = true; track++; } } // Start from 2nd line check if any word of // the first string did not match with // some word in the current line for (j = 1; j < m; j++) { has.clear(); i = 0; while (i < s[j].length) { str = ""; while (i < s[j].length && s[j].charAt(i) != ' ') { str += s[j].charAt(i); i++; } i++; if (str !== "") has.set(str, true); } // Check all words of this vector // if it is not present in current line // make it false for (k = 0; k < track; k++) { // document.write(has.get(ans1[k])); if (ans2[k] != false && !has.has(ans1[k])) ans2[k] = false; // This line is used to consider // only distinct words else if (ans2[k] != false && has.has(ans1[k]) && has.get(ans1[k]) == true) has.set(ans1[k], false); } } // This function will print // the count of common words var cnt = 0; // If current word appears // in all the sentences for (k = 0; k < track; k++) if (ans2[k] == true) cnt++; return cnt; } // Driver Code var s = [ "there is a cow", "cow is our mother", "cow gives us milk and milk is sweet", "there is a boy who loves cow" ]; document.write(commonWords(s));// This code is contributed by gauravrajput1</script> |
Output
2
The time complexity of the given implementation is O(nmk), where n is the average length of a sentence, m is the number of sentences, and k is the average length of a word.
The auxiliary space used by the algorithm is also O(nmk)
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!
