Given a string S representing a sentence and another string word, the task is to find the word from S which has the string word as a prefix. If no such word is present in the string, print -1.
Examples:
Input: S = “Welcome to Geeksforneveropen”, word=”Gee”
Output: Geeksforneveropen
Explanation:
The word “Geeksforneveropen” in the sentence has the prefix “Gee”.Input: s=”Competitive Programming”, word=”kdflk”
Output: -1
Explanation:
No word in the string has “kdflk” as its prefix.
Approach: Follow the steps below to find which word has the given prefix:
- Extract the words from the sentence using the stringstream and store them in a vector of strings.
- Now, traverse the array and check which word contains the given word as its own prefix.
- If found to be true for any word, then print that word. Otherwise, if no such word is found, print -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the position// of the string having word as prefixstring isPrefixOfWord(string sentence, string Word){ stringstream ss(sentence); // Initialize a vector vector<string> v; string temp; // Extract words from the sentence while (ss >> temp) { v.push_back(temp); } // Traverse each word for (int i = 0; i < v.size(); i++) { // Traverse the characters of word for (int j = 0; j < v[i].size(); j++) { // If prefix does not match if (v[i][j] != Word[j]) break; // Otherwise else if (j == Word.size() - 1) // Return the word return v[i]; } } // Return -1 if not present return "-1";}// Driver codeint main(){ string s = "Welcome to Geeksforneveropen"; string word = "Gee"; cout << isPrefixOfWord(s, word) << endl; return 0;} |
Java
// Java program for the above approach import java.util.*;import java.io.*;import java.lang.Math;class GFG{ // Function to find the position // of the string having word as prefix static String isPrefixOfWord(String sentence, String Word) { String a[] = sentence.split(" "); // Initialize an ArrayList ArrayList<String> v = new ArrayList<>(); // Extract words from the sentence for(String e : a) v.add(e); // Traverse each word for(int i = 0; i < v.size(); i++) { // Traverse the characters of word for(int j = 0; j < v.get(i).length(); j++) { // If prefix does not match if (v.get(i).charAt(j) != Word.charAt(j)) break; // Otherwise else if (j == Word.length() - 1) // Return the word return v.get(i); } } // Return -1 if not present return "-1"; } // Driver code public static void main(final String[] args) { String s = "Welcome to Geeksforneveropen"; String word = "Gee"; System.out.println(isPrefixOfWord(s, word));}}// This code is contributed by bikram2001jha |
Python3
# Python3 program for the # above approach# Function to find the # position of the string # having word as prefixdef isPrefixOfWord(sentence, word): a=sentence.split(" ") # Initialize an List v = [] # Extract words from # the sentence for i in a: v.append(i) # Traverse each word for i in range(len(v)): # Traverse the characters of word for j in range(len(v[i])): # If prefix does not match if(v[i][j] != word[j]): break # Otherwise elif(j == len(word) - 1): # Return the word return v[i] # Return -1 if not present return -1# Driver code s = "Welcome to Geeksforneveropen"word = "Gee"print(isPrefixOfWord(s, word))# This code is contributed by avanitrachhadiya2155 |
C#
// C# program for the above approach using System;using System.Collections.Generic;class GFG{ // Function to find the position // of the string having word as prefix static String isPrefixOfWord(String sentence, String Word) { String []a = sentence.Split(' '); // Initialize an List List<String> v = new List<String>(); // Extract words from the sentence foreach(String e in a) v.Add(e); // Traverse each word for(int i = 0; i < v.Count; i++) { // Traverse the characters of word for(int j = 0; j < v[i].Length; j++) { // If prefix does not match if (v[i][j] != Word[j]) break; // Otherwise else if (j == Word.Length - 1) // Return the word return v[i]; } } // Return -1 if not present return "-1"; } // Driver code public static void Main(String[] args) { String s = "Welcome to Geeksforneveropen"; String word = "Gee"; Console.WriteLine(isPrefixOfWord(s, word));}}// This code is contributed by Rajput-Ji |
Javascript
<script>//Javascript program for the above approach// Function to find the position // of the string having word as prefix function isPrefixOfWord(sentence, Word) { var a = sentence.split(" "); // Initialize an ArrayList var v = []; // Extract words from the sentence //for(String e : a) for(var i=0;i<a.length;i++) { v.push(a[i]); } // Traverse each word for(var i = 0; i < v.length; i++) { // Traverse the characters of word for(var j = 0; j < v[i].length; j++) { // If prefix does not match if (v[i].charAt(j) != Word[j]) break; // Otherwise else if (j == Word.length- 1) // Return the word return v[i]; } } // Return -1 if not present return "-1"; } var s = "Welcome to Geeksforneveropen"; var word = "Gee"; document.write(isPrefixOfWord(s, word));//This code in contributed by SoumikMondal</script> |
Output:
Geeksforneveropen
Time Complexity: O(L), where L denotes the length of the string S
Auxiliary Space: O(L)
Approach: Follow the steps below to find which word has the given prefix:
1. Using the split() function, to extract word from the sentences
2. We use in operator to check presence of substring
C++
#include <iostream>#include <string>#include <vector>#include <sstream>using namespace std;string prefix(string sentence, string word){ // Converting the string into an array of words // using the stringstream and getline() method vector<string> l; stringstream ss(sentence); string temp; while (ss >> temp) { l.push_back(temp); } // Initializing the variable to store // the last word containing the prefix string c = "-1"; // Looping through each word in the array for (string i : l) { // Checking if the prefix is a substring of // the current word using the find() method if (i.find(word) != string::npos) { c = i; } } // Returning the last word containing the prefix or -1 if not found return c;}// Driver codeint main() { string s = "Welcome to Geeksforneveropen"; string word = "Gee"; cout << prefix(s, word) << endl; // Outputs "Geeksforneveropen" return 0;} |
Java
import java.util.*;public class Main { static String prefix(String sentence, String word) { // Converting the string into an array of words using the split() method String[] l = sentence.split(" "); // Initializing the variable to store the last word containing the prefix String c = "-1"; // Looping through each word in the array for (String i : l) { // Checking if the prefix is a substring of the current word using the contains() method if (i.contains(word)) { c = i; } } // Returning the last word containing the prefix or -1 if not found return c; } // Driver code public static void main(String[] args) { String s = "Welcome to Geeksforneveropen"; String word = "Gee"; System.out.println(prefix(s, word)); // Outputs "Geeksforneveropen" }} |
Python3
def prefix(sentence, word): # converting string into list l=sentence.split() c=-1 for i in l: # in operator to check substring if word in i: c=i # Returning the substring or -1 return c# input string s = "Welcome to Geeksforneveropen"#prefix word = "Gee"print(prefix(s, word))# This code is contributed by Asif shaik |
C#
//C# codeusing System;public class Program{ // Function to return the last word that contains the given prefix static string Prefix(string sentence, string word) { // Converting the string into an array of words using the Split() method string[] l = sentence.Split(" "); // Initializing the variable to store the last word containing the prefix string c = "-1"; // Looping through each word in the array foreach (string i in l) { // Checking if the prefix is a substring of the current word using the Contains() method if (i.Contains(word)) { c = i; } } // Returning the last word containing the prefix or -1 if not found return c; } // Driver code public static void Main() { string s = "Welcome to Geeksforneveropen"; string word = "Gee"; Console.WriteLine(Prefix(s, word)); // Outputs "Geeksforneveropen" }} |
Javascript
function prefix(sentence, word) { // Converting the string into an array of words using the split() method let l = sentence.split(" "); // Initializing the variable to store the last word containing the prefix let c = -1; // Looping through each word in the array for (let i of l) { // Checking if the prefix is a substring of the current word using the includes() method if (i.includes(word)) { c = i; } } // Returning the last word containing the prefix or -1 if not found return c;}// Input stringlet s = "Welcome to Geeksforneveropen";// Prefixlet word = "Gee";console.log(prefix(s, word)); // Outputs "Geeksforneveropen" |
Output
Geeksforneveropen
Time Complexity: O(L), where L denotes the length of the string S
Auxiliary Space: O(L)
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!
