Given a string S and a list lis[] of N number of words, the task is to find every possible (N+1)th word from string S such that the ‘second’ word comes immediately after the ‘first’ word, the ‘third’ word comes immediately after the ‘second’ word, the ‘fourth’ word comes immediately after the ‘third’ word and so on.
Examples:
Input: S = “Siddhesh is a smart guy the city he lives in is a smart city”, lis: [“is”, “a”, “smart”]
Output: [guy, city]
Explanation: Here the two sequences where the words occur
just as the pattern mentioned are.
- is a smart guy
- is a smart city
Hence we found ‘guy’ and ‘city’ as the desired words.
Input: S = “David loves to play and David loves to write sometimes”, lis: [“loves”, “to”]
Output: [play, write]
Approach: The simplest way to solve the problem is:
Break the whole string into words separated by spaces and Iterate over these words and match (i)th, (i+1)th, . . . (i+N-1)th word with the first, second, . . ., Nth words given, If the words matched store the (i+N)th word in a list.
Follow the steps to solve the problem:
- Split the given string S by spaces.
- Create a list ‘res‘ to store the ‘N+1’th words in the string.
- Now, iterate through the split string from i = 0.
- Check every (i)th, (i+1)th, . . ., (i+N-1)th indices in every iteration, whether they are equal to the ‘first’, ‘second’, . . ., ‘N’th words respectively or not.
- If yes then append the (N+1)th word to the answer list.
- Return the list storing the words as the required answer.
Below is the implementation for the above idea:
C++
// C++ program for the above approach:#include <bits/stdc++.h>using namespace std;vector<string> findOcurrences(string s, vector<string>& lis){ // Split the given string // by default split function splits the // string by spaces and stores the // splitted words in a list vector<string> temp_lis; string temp_str = ""; for (int i = 0; i < s.size(); ++i) { if (s[i] == ' ') { temp_lis.push_back(temp_str); temp_str = ""; } else temp_str += s[i]; } if (temp_str != "") temp_lis.push_back(temp_str); vector<string> res; int N = lis.size(); // Loop to find the matching string // and the last word string join_lis = ""; for (auto str : lis) join_lis += str; for (int i = 0; i < temp_lis.size() - N; ++i) { string join_temp_lis = ""; for (int j = i; j < i + N; ++j) join_temp_lis += temp_lis[j]; if (join_lis == join_temp_lis) res.push_back(temp_lis[i + N]); } // Return the answer list return res;}// Driver codeint main(){ string s = "Siddhesh is a smart guy the city he lives " "in is a smart city"; vector<string> lis = { "is", "a", "smart" }; // Function call vector<string> final_list = findOcurrences(s, lis); for (auto st : final_list) cout << st << " "; return 0;} // This code is contributed by rakeshsahni |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { public static ArrayList<String> findOcurrences(String s, ArrayList<String> lis) { // Split the given string // by default split function splits the // string by spaces and stores the // splitted words in a list ArrayList<String> temp_lis = new ArrayList<String>(); String temp_str = ""; for (int i = 0; i < s.length(); ++i) { if (s.charAt(i) == ' ') { temp_lis.add(temp_str); temp_str = ""; } else temp_str += s.charAt(i); } if (temp_str != "") temp_lis.add(temp_str); ArrayList<String> res = new ArrayList<String>(); int N = lis.size(); // Loop to find the matching string // and the last word String join_lis = ""; for (int str = 0; str < lis.size(); str++) join_lis += lis.get(str); for (int i = 0; i < temp_lis.size() - N; ++i) { String join_temp_lis = new String(); for (int j = i; j < i + N; ++j) join_temp_lis += temp_lis.get(j); if (join_lis.equals(join_temp_lis)) res.add(temp_lis.get(i + N)); } return res; } public static void main(String[] args) { String s = "Siddhesh is a smart guy the city he lives in is a smart city"; ArrayList<String> lis = new ArrayList<String>(); lis.add("is"); lis.add("a"); lis.add("smart"); // Function call System.out.println(findOcurrences(s, lis)); }}// This code is contributed by akashish__ |
Python3
# Python program for the above approach:def findOcurrences(string, lis): # Split the given string # by default split function splits the # string by spaces and stores the # splitted words in a list temp_lis = string.split() res = [] N = len(lis) # Loop to find the matching string # and the last word for i in range(len(temp_lis)-N): if ''.join(lis) == ''.join(temp_lis[i:i + N]): res.append(temp_lis[i + N]) # Return the answer list return res# Driver codeif __name__ == '__main__': string = "Siddhesh is a smart guy the city he lives in is a smart city" lis = ["is", "a", "smart"] # Function call final_list = findOcurrences(string, lis) print(final_list) |
C#
using System;using System.Collections.Generic;public class GFG { public static string findOcurrences(string s, string[] lis) { // Split the given string // by default split function splits the // string by spaces and stores the // splitted words in a list List<string> temp_lis = new List<string>(); string temp_str = ""; for (int i = 0; i < s.Length; ++i) { if (s[i] == ' ') { temp_lis.Add(temp_str); temp_str = ""; } else temp_str += s[i]; } if (temp_str != "") temp_lis.Add(temp_str); List<string> res = new List<string>(); int N = lis.Length; // Loop to find the matching string // and the last word string join_lis = ""; for (int str = 0; str < lis.Length; str++) join_lis += lis[str]; for (int i = 0; i < temp_lis.Count - N; ++i) { string join_temp_lis = ""; for (int j = i; j < i + N; ++j) join_temp_lis += temp_lis[j]; if (join_lis == join_temp_lis) res.Add(temp_lis[i + N]); } // Return the answer list return string.Join(" ", res); } static public void Main() { // Code string s = "Siddhesh is a smart guy the city he lives in is a smart city"; string[] lis = { "is", "a", "smart" }; // Function call string final_list = (findOcurrences(s, lis)); for (int st = 0; st < final_list.Length; st++) Console.Write(final_list[st]); }}// This code is contributed by akashish__ |
Javascript
<script> // Javascript program for the above approach:function findOcurrences(string, lis){ // Split the given string // by default split function splits the // string by spaces and stores the // splitted words in a list let temp_lis = string.split(" "); let res = []; let N = lis.length; // Loop to find the matching string // and the last word for(let i=0;i<temp_lis.length-N;i++) { if(lis.join('') == temp_lis.slice(i,i+N).join('')) { res.push(temp_lis[i+N]); } } // Return the answer list return res;}// Driver codelet string = "Siddhesh is a smart guy the city he lives in is a smart city";let lis = ["is", "a", "smart"];// Function calllet final_list = findOcurrences(string, lis);console.log(final_list);// This code is contributed by akashish__</script> |
Output
guy city
Time Complexity: O(N * K * d) where K is the size of the string and d is the maximum size of a word
Auxiliary Space: O(N)
Another Approach:- Using Two Pointers
- We can simply take all words present in String s.
- After this we can iterator on all words and can match it with words given in list.
- If at a time all words of list got matched then the next word from the string will be in our answer.
- Return all words meet the following criteria.
Implementation:-
C++
// C++ program for the above approach:#include <bits/stdc++.h>using namespace std;vector<string> findOcurrences(string s, vector<string>& lis){ // Split the given string // by default split function splits the // string by spaces and stores the // splitted words in a list vector<string> temp_lis; string temp_str = ""; for (int i = 0; i < s.size(); ++i) { if (s[i] == ' ') { temp_lis.push_back(temp_str); temp_str = ""; } else temp_str += s[i]; } if (temp_str != "") temp_lis.push_back(temp_str); vector<string> res; int N = lis.size(), j = 0; // matching word of lis and temp_lis for (int i = 0; i < temp_lis.size(); i++) { // if all word got matched then take the next into // answer if (j == N) { res.push_back(temp_lis[i]); j = 0; continue; } // if current word got matched go to the next word if (temp_lis[i] == lis[j]) j++; // else start matching from start word else j = 0; } // Return the answer list return res;}// Driver codeint main(){ string s = "Siddhesh is a smart guy the city he lives " "in is a smart city"; vector<string> lis = { "is", "a", "smart" }; // Function call vector<string> final_list = findOcurrences(s, lis); for (auto st : final_list) cout << st << " "; return 0;}// This code is contributed by shubhamrajput6156 |
Java
import java.util.ArrayList;import java.util.List;public class Main { public static List<String> findOccurrences(String s, List<String> lis) { // Split the given string by spaces String[] tempArr = s.split(" "); List<String> tempList = new ArrayList<>(); for (String str : tempArr) { tempList.add(str); } List<String> result = new ArrayList<>(); int N = lis.size(); int j = 0; // Match words from lis and tempList for (int i = 0; i < tempList.size(); i++) { // If all words from lis have been matched, add the next word to the result if (j == N) { result.add(tempList.get(i)); j = 0; continue; } // If the current word matches the word from lis, move to the next word if (tempList.get(i).equals(lis.get(j))) { j++; } // Otherwise, start matching from the first word in lis else { j = 0; } } // Return the result list return result; } public static void main(String[] args) { String s = "Siddhesh is a smart guy the city he lives in is a smart city"; List<String> lis = new ArrayList<>(); lis.add("is"); lis.add("a"); lis.add("smart"); // Function call List<String> finalList = findOccurrences(s, lis); for (String st : finalList) { System.out.print(st + " "); } }} |
Python3
import redef findOcurrences(s, lis): # Split the given string # by default split function splits the # string by spaces and stores the # splitted words in a list temp_lis = re.findall(r'\w+', s) res = [] N = len(lis) j = 0 # matching word of lis and temp_lis for i in range(len(temp_lis)): # if all word got matched then take the next into answer if j == N: res.append(temp_lis[i]) j = 0 continue # if current word got matched go to the next word if temp_lis[i] == lis[j]: j += 1 # else start matching from start word else: j = 0 # Return the answer list return res# Test cases = "Siddhesh is a smart guy the city he lives in is a smart city"lis = ["is", "a", "smart"]final_list = findOcurrences(s, lis)for st in final_list: print(st, end=" ") |
C#
using System;using System.Collections.Generic;class Gfg{ static List<string> FindOcurrences(string s, List<string> lis) { // Split the given string by spaces string[] temp_lis = s.Split(' '); List<string> res = new List<string>(); int N = lis.Count, j = 0; // Matching word of lis and tempLis for (int i = 0; i < temp_lis.Length; i++) { // If all words got matched, then take the next word into the answer if (j == N) { res.Add(temp_lis[i]); j = 0; continue; } // If current word got matched, go to the next word if (temp_lis[i] == lis[j]) j++; // Else start matching from the start word else j = 0; } // Return the answer list return res; } static void Main(string[] args) { string s = "Siddhesh is a smart guy the city he lives in is a smart city"; List<string> lis = new List<string> { "is", "a", "smart" }; // Function call List<string> final_list = FindOcurrences(s, lis); foreach (string st in final_list) Console.Write(st + " "); }} |
Javascript
const findOcurrences = (s, lis) => { // Split the given string // by default split function splits the // string by spaces and stores the // splitted words in a list const temp_lis = s.match(/\w+/g); const res = []; const N = lis.length; let j = 0; // matching word of lis and temp_lis for (let i = 0; i < temp_lis.length; i++) { // if all word got matched then take the next into // answer if (j === N) { res.push(temp_lis[i]); j = 0; continue; } // if current word got matched go to the next word if (temp_lis[i] === lis[j]) { j += 1; } // else start matching from start word else { j = 0; } } // Return the answer list return res;};// Test caseconst s = "Siddhesh is a smart guy the city he lives in is a smart city";const lis = ["is", "a", "smart"];const final_list = findOcurrences(s, lis);for (const st of final_list) { console.log(st, end=" ");} |
Output
guy city
Time Complexity:- O(M) where M is the size of string s
Space Complexity:- O(M)
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!
