Sentence that contains all the given phrases
Given a list of sentences and a list of phrases. The task is to find which sentence(s) contain all the words in a phrase and for every phrase print the sentences number that contains the given phrase. Constraint: A word cannot be a part of more than 10 sentences. Examples:
Input:
Sentences: 1. Strings are an array of characters. 2. Sentences are an array of words.
Phrases: 1. an array of 2. sentences are strings
Output: Phrase1 is present in sentences: 1,2 Phrase2 is present in sentences: None Since each word in phrase 1 exists in both the sentences, but all the words in second phrase do not exist in either.
Input:
Sentences: 1. Sets in python are a hash table representation of arrays. 2. Searching in Sets are a function of time complexity O(1). 3. Sets only contain unique elements, and have no order.
Phrases: 1. Sets are a 2. Searching in
Output: Phrase1 is present in sentences: 1, 2 Phrase2 is present in sentences: 2
Approach: For each Phrase, we have to find the sentences which contain all the words of the phrase. So, for each word in the given phrase, we check if a sentence contains it. We do this for each sentence. This process of searching may become faster if the words in the sentence are stored in a set instead of a list. Below is the implementation of above approach:
C++
// C++ program to find the sentence // that contains all the given phrases #include <bits/stdc++.h> using namespace std; void getRes(vector<string> sent, vector<string> ph) { map<string, multiset<string> > sentHash; // Loop for adding hashed sentences to sentHash for ( auto s : sent) { int j = 0; for ( int i = 0; i < s.size(); i++) { if (s[i] == ' ' ) { sentHash[s].insert(s.substr(j, i - j)); j = i + 1; } } } for ( int p = 0; p < ph.size(); p++) { cout << "Phrase" << (p + 1) << ":" << endl; // Get the list of Words vector<string> wordList; int j = 0; for ( int i = 0; i < ph[p].size(); i++) { if (ph[p][i] == ' ' ) { wordList.push_back(ph[p].substr(j, i - j)); j = i + 1; } } vector< int > res; // Then Check in every Sentence for ( int s = 0; s < sent.size(); s++) { int wCount = wordList.size(); // Every word in the Phrase for (string w : wordList) { if (sentHash[sent[s]].find(w) != sentHash[sent[s]].end()) { wCount--; } } // If every word in phrase matches if (wCount == 0) { // add Sentence Index to result Array res.push_back(s + 1); } } if (res.size() == 0) { cout << ( "NONE" ) << endl; } else { for ( int i : res) { cout << i << " " ; } cout << endl; } } } // Driver Code int main() { vector<string> sent{ "Strings are an array of characters" , "Sentences are an array of words" }; vector<string> ph{ "an array of" , "sentences are strings" }; getRes(sent, ph); } // This code is contributed by garg28harsh. |
Java
// Java program to find the sentence // that contains all the given phrases import java.io.*; import java.util.*; class GFG { static void getRes(String[] sent, String[] ph) { HashMap<String, HashSet<String> > sentHash = new HashMap<>(); // Loop for adding hashed sentences to sentHash for (String s : sent) { HashSet<String> set = new HashSet<>( Arrays.asList(s.split( " " ))); sentHash.put(s, set); } for ( int p = 0 ; p < ph.length; p++) { System.out.println( "Phrase" + (p + 1 ) + ":" ); // Get the list of Words String[] wordList = ph[p].split( " " ); ArrayList<Integer> res = new ArrayList<>(); // Then Check in every Sentence for ( int s = 1 ; s <= sent.length; s++) { int wCount = wordList.length; // Every word in the Phrase for (String w : wordList) { if (sentHash.get(sent[s - 1 ]) .contains(w)) { wCount--; } } // If every word in phrase matches if (wCount == 0 ) { // add Sentence Index to result Array res.add(s); } } if (res.size() == 0 ) { System.out.println( "NONE" ); } else { for (Integer i : res) { System.out.print(i + " " ); } System.out.println(); } } } // Driver Code public static void main(String[] args) { String[] sent = { "Strings are an array of characters" , "Sentences are an array of words" }; String[] ph = { "an array of" , "sentences are strings" }; getRes(sent, ph); } } // This code is contributed by Karandeep1234 |
Python3
# Python program to find the sentence # that contains all the given phrases def getRes(sent, ph): sentHash = dict () # Loop for adding hashed sentences to sentHash for s in range ( 1 , len (sent) + 1 ): sentHash[s] = set (sent[s - 1 ].split()) # For Each Phrase for p in range ( 0 , len (ph)): print ("Phrase" + str (p + 1 ) + ":") # Get the list of Words wordList = ph[p].split() res = [] # Then Check in every Sentence for s in range ( 1 , len (sentHash) + 1 ): wCount = len (wordList) # Every word in the Phrase for w in wordList: if w in sentHash[s]: wCount - = 1 # If every word in phrase matches if wCount = = 0 : # add Sentence Index to result Array res.append(s) if ( len (res) = = 0 ): print ("NONE") else : print ( '% s' % ' ' .join( map ( str , res))) # Driver Function def main(): sent = ["Strings are an array of characters", "Sentences are an array of words"] ph = ["an array of", "sentences are strings"] getRes(sent, ph) main() |
C#
// C# program to find the sentence // that contains all the given phrases using System; using System.Collections.Generic; class Program { static void Main( string [] args) { List< string > sent = new List< string >() { "Strings are an array of characters" , "Sentences are an array of words" }; List< string > ph = new List< string >() { "an array of" , "sentences are strings" }; GetRes(sent, ph); } static void GetRes(List< string > sent, List< string > ph) { Dictionary< string , SortedSet< string >> sentHash = new Dictionary< string , SortedSet< string >>(); // Loop for adding hashed sentences to sentHash foreach ( string s in sent) { int j = 0; for ( int i = 0; i < s.Length; i++) { if (s[i] == ' ' ) { if (!sentHash.ContainsKey(s)) sentHash[s] = new SortedSet< string >(); sentHash[s].Add(s.Substring(j, i - j)); j = i + 1; } } } for ( int p = 0; p < ph.Count; p++) { Console.WriteLine($ "Phrase {p + 1}:" ); // Get the list of Words List< string > wordList = new List< string >(); int j = 0; for ( int i = 0; i < ph[p].Length; i++) { if (ph[p][i] == ' ' ) { wordList.Add(ph[p].Substring(j, i - j)); j = i + 1; } } List< int > res = new List< int >(); // Then Check in every Sentence for ( int s = 0; s < sent.Count; s++) { int wCount = wordList.Count; // Every word in the Phrase foreach ( string w in wordList) { if (sentHash[sent[s]].Contains(w)) { wCount--; } } // If every word in phrase matches if (wCount == 0) { // add Sentence Index to result Array res.Add(s + 1); } } if (res.Count == 0) { Console.WriteLine( "NONE" ); } else { foreach ( int i in res) { Console.Write(i + " " ); } Console.WriteLine(); } } } } //This code is contributed bt Chetan Bargal |
Javascript
// JavaScript program to find the sentence // that contains all the given phrases function getRes(sent, ph) { let sentHash = {}; // Loop for adding hashed sentences to sentHash for (let s = 1; s <= sent.length; s++) { sentHash[s] = new Set(sent[s-1].split( " " )); } // For Each Phrase for (let p = 0; p < ph.length; p++) { console.log(`Phrase${p+1}:`); // Get the list of Words let wordList = ph[p].split( " " ); let res = []; // Then Check in every Sentence for (let s = 1; s <= Object.keys(sentHash).length; s++) { let wCount = wordList.length; // Every word in the Phrase for (let w of wordList) { if (sentHash[s].has(w)) { wCount--; } } // If every word in phrase matches if (wCount === 0) { // add Sentence Index to result Array res.push(s); } } if (res.length === 0) { console.log( "NONE" ); } else { console.log(res.join( " " )); } } } // Driver Function function main() { let sent = [ "Strings are an array of characters" , "Sentences are an array of words" ]; let ph = [ "an array of" , "sentences are strings" ]; getRes(sent, ph); } main(); |
Phrase1: 1 2 Phrase2: NONE
Time complexity: O(SPW)
Space complexity: O(SW)
where S is the number of sentences and W is the average number of words per sentence and P is the number of phrases and W is the average number of words per phrase.