Dada una string, encuentre la primera palabra repetida en una string
Ejemplos:
Input : "Ravi had been saying that he had been there" Output : had Input : "Ravi had been saying that" Output : No Repetition Input : "he had had he" Output : he
fuente de la pregunta: https://www.geeksforgeeks.org/goldman-sachs-interview-experience-set-29-internship/
Enfoque simple: comience a iterar desde atrás y para cada palabra nueva, guárdela en un mapa desordenado. Por cada palabra que haya ocurrido más de una, actualice ans para que sea esa palabra, por último invierta ans e imprímala.
Implementación:
C++
// Cpp program to find first repeated word in a string #include<bits/stdc++.h> using namespace std; void solve(string s) { unordered_map<string,int> mp; // to store occurrences of word string t="",ans=""; // traversing from back makes sure that we get the word which repeats first as ans for(int i=s.length()-1;i>=0;i--) { // if char present , then add that in temp word string t if(s[i]!=' ') { t+=s[i]; } // if space is there then this word t needs to stored in map else { mp[t]++; // if that string t has occurred previously then it is a possible ans if(mp[t]>1) ans=t; // set t as empty for again new word t=""; } } // first word like "he" needs to be mapped mp[t]++; if(mp[t]>1) ans=t; if(ans!="") { // reverse ans string as it has characters in reverse order reverse(ans.begin(),ans.end()); cout<<ans<<'\n'; } else cout<<"No Repetition\n"; } int main() { string u="Ravi had been saying that he had been there"; string v="Ravi had been saying that"; string w="he had had he"; solve(u); solve(v); solve(w); return 0; }
Java
import java.util.*; public class GFG { // Java program to find first repeated word in a string public static void solve(String s) { HashMap<String, Integer> mp = new HashMap<String, Integer>(); // to store // occurrences of word String t = ""; String ans = ""; // traversing from back makes sure that we get the // word which repeats first as ans for (int i = s.length() - 1; i >= 0; i--) { // if char present , then add that in temp word // string t if (s.charAt(i) != ' ') { t += s.charAt(i); } // if space is there then this word t needs to // stored in map else { if (!mp.containsKey(t)) { mp.put(t, 1); } else { mp.put(t, mp.get(t) + 1); } // if that string t has occurred previously // then it is a possible ans if (mp.get(t) > 1) { ans = t; } // set t as empty for again new word t = ""; } } // first word like "he" needs to be mapped if (!mp.containsKey(t)) { mp.put(t, 1); } else { mp.put(t, mp.get(t) + 1); } if (mp.get(t) > 1) { ans = t; } if (!ans.equals("")) { // reverse ans string as it has characters in // reverse order StringBuilder input1 = new StringBuilder(); // append a string into StringBuilder input1 input1.append(ans); // reverse StringBuilder input1 input1.reverse(); System.out.println(input1); } else { System.out.print("No Repetition\n"); } } public static void main(String[] args) { String u = "Ravi had been saying that he had been there"; String v = "Ravi had been saying that"; String w = "he had had he"; solve(u); solve(v); solve(w); } } // This code is contributed by Aarti_Rathi
Python3
# Python program to find first repeated word in a string def solve(s): mp = {} # to store occurrences of word t = "" ans = "" # traversing from back makes sure that we get the word which repeats first as ans for i in range(len(s) - 1,-1,-1): # if char present , then add that in temp word string t if(s[i] != ' '): t += s[i] # if space is there then this word t needs to stored in map else: # if that string t has occurred previously then it is a possible ans if(t in mp): ans = t else: mp[t] = 1 # set t as empty for again new word t = "" # first word like "he" needs to be mapped if(t in mp): ans=t if(ans!=""): # reverse ans string as it has characters in reverse order ans = ans[::-1] print(ans) else: print("No Repetition") # driver code u = "Ravi had been saying that he had been there" v = "Ravi had been saying that" w = "he had had he" solve(u) solve(v) solve(w) # This code is contributed by shinjanpatra
C#
// C# program to find first repeated word in a string using System; using System.Collections.Generic; class GFG { static void solve(string s) { Dictionary<string, int> mp = new Dictionary< string, int>(); // to store occurrences of word string t = ""; string ans = ""; // traversing from back makes sure that we get the // word which repeats first as ans for (int i = s.Length - 1; i >= 0; i--) { // if char present , then add that in temp word // string t if (s[i] != ' ') { t += s[i]; } // if space is there then this word t needs to // stored in map else { if (mp.ContainsKey(t)) { mp[t] += 1; } else { mp.Add(t, 1); } // if that string t has occurred previously // then it is a possible ans if (mp[t] > 1) { ans = t; } // set t as empty for again new word t = ""; } } // first word like "he" needs to be mapped if (mp.ContainsKey(t)) { mp[t] += 1; } else { mp.Add(t, 1); } if (mp[t] > 1) { ans = t; } if (ans != "") { // reverse ans string as it has characters in // reverse order char[] charArray = ans.ToCharArray(); Array.Reverse(charArray); Console.WriteLine(new string(charArray)); } else { Console.Write("No Repetition\n"); } } public static void Main() { string u = "Ravi had been saying that he had been there"; string v = "Ravi had been saying that"; string w = "he had had he"; solve(u); solve(v); solve(w); } } // This code is contributed by Aarti_Rathi
Javascript
<script> // JavaScript program to find first repeated word in a string function solve(s) { let mp = new Map(); // to store occurrences of word let t = ""; let ans = ""; // traversing from back makes sure that we get the word which repeats first as ans for(let i = s.length - 1; i >= 0; i--) { // if char present , then add that in temp word string t if(s[i] != ' ') { t += s[i]; } // if space is there then this word t needs to stored in map else { // if that string t has occurred previously then it is a possible ans if(mp.has(t)) ans = t; else mp.set(t, 1) // set t as empty for again new word t = ""; } } // first word like "he" needs to be mapped if(mp.has(t)) ans=t; if(ans!="") { // reverse ans string as it has characters in reverse order ans = [...ans].reverse().join(""); document.write(ans); } else document.write("No Repetition"); } // driver code const u = "Ravi had been saying that he had been there"; const v = "Ravi had been saying that"; const w = "he had had he"; solve(u); solve(v); solve(w); // This code is contributed by shinjanpatra </script>
had No Repetition he
Otro enfoque: la idea es tokenizar la string y almacenar cada palabra y su conteo en hashmap. Luego, recorra la string nuevamente y para cada palabra de la string, verifique su conteo en el hashmap creado.
Implementación:
CPP
// CPP program for finding first repeated // word in a string #include <bits/stdc++.h> using namespace std; // returns first repeated word string findFirstRepeated(string s) { // break string into tokens // and then each string into set // if a word appeared before appears // again, return the word and break istringstream iss(s); string token; // hashmap for storing word and its count // in sentence unordered_map<string, int> setOfWords; // store all the words of string // and the count of word in hashmap while (getline(iss, token, ' ')) { if (setOfWords.find(token) != setOfWords.end()) setOfWords[token] += 1; // word exists else // insert new word to set setOfWords.insert(make_pair(token, 1)); } // traverse again from first word of string s // to check if count of word is greater than 1 // either take a new stream or store the words // in vector of strings in previous loop istringstream iss2(s); while (getline(iss2, token, ' ')) { int count = setOfWords[token]; if (count > 1) { return token; } } return "NoRepetition"; } // driver program int main() { string s("Ravi had been saying that he had been there"); string firstWord = findFirstRepeated(s); if (firstWord != "NoRepetition") cout << "First repeated word :: " << firstWord << endl; else cout << "No Repetitionn"; return 0; }
Java
// Java program for finding first repeated // word in a string import java.util.*; class GFG{ // returns first repeated word static String findFirstRepeated(String s) { // break string into tokens // and then each string into set // if a word appeared before appears // again, return the word and break String token[] = s.split(" "); // hashmap for storing word and its count // in sentence HashMap<String, Integer> setOfWords = new HashMap<String, Integer>(); // store all the words of string // and the count of word in hashmap for (int i=0; i<token.length; i++) { if (setOfWords.containsKey(token[i])) setOfWords.put(token[i], setOfWords.get(token[i]) + 1); // word exists else // insert new word to set setOfWords.put(token[i], 1); } // traverse again from first word of string s // to check if count of word is greater than 1 // either take a new stream or store the words // in vector of strings in previous loop for (int i=0; i<token.length; i++) { int count = setOfWords.get(token[i]); if (count > 1) { return token[i]; } } return "NoRepetition"; } // driver program public static void main(String args[]) { String s = "Ravi had been saying that he had been there"; String firstWord = findFirstRepeated(s); if (!firstWord.equals("NoRepetition")) System.out.println("First repeated word :: " + firstWord); else System.out.println("No Repetitionn"); } }
Javascript
class GFG { // returns first repeated word static findFirstRepeated(s) { // break string into tokens // and then each string into set // if a word appeared before appears // again, return the word and break var token = s.split(" "); // map for storing word and its count // in sentence var setOfWords = new Map(); // store all the words of string // and the count of word in map for (let i=0; i < token.length; i++) { if (setOfWords.has(token[i])) { setOfWords.set(token[i],setOfWords.get(token[i]) + 1); } else { // insert new word to map setOfWords.set(token[i],1); } } // traverse again from first word of string s // to check if count of word is greater than 1 // either take a new stream or store the words // in array of strings in previous loop for (let i=0; i < token.length; i++) { var count = setOfWords.get(token[i]); if (count > 1) { return token[i]; } } return "NoRepetition"; } // driver program static main(args) { var s = "Ravi had been saying that he had been there"; var firstWord = GFG.findFirstRepeated(s); if (firstWord !== "NoRepetition") { console.log("First repeated word :: " + firstWord); } else { console.log("No Repetitionn"); } } } GFG.main([]); // This code is contributed by mukulsomukesh
First repeated word::had
Método n.º 2: uso de funciones integradas de python:
- Como todas las palabras en una oración están separadas por espacios.
- Tenemos que dividir la oración por espacios usando split().
- Dividimos todas las palabras por espacios y las almacenamos en una lista.
- Utilice la función de contador para contar la frecuencia de las palabras
- Recorre la lista y comprueba si alguna palabra tiene una frecuencia superior a 1
- Si está presente, imprima la palabra y rompa el bucle.
Implementación: :
Python3
# Python program for the above approach from collections import Counter # Python program to find the first # repeated character in a string def firstRepeatedWord(sentence): # splitting the string lis = list(sentence.split(" ")) # Calculating frequency of every word frequency = Counter(lis) # Traversing the list of words for i in lis: # checking if frequency is greater than 1 if(frequency[i] > 1): # return the word return i # Driver code sentence = "Vikram had been saying that he had been there" print(firstRepeatedWord(sentence)) # this code is contributed by vikkycirus
had
Otro enfoque:
En lugar de realizar un seguimiento de los recuentos de una ficha (palabra) específica, podemos realizar un seguimiento de la primera aparición de la ficha (palabra) mediante un mapa desordenado. Esto no requeriría ningún bucle adicional para atravesar un hashmap o una string para encontrar la string repetida. Por lo tanto, eventualmente transforma la complejidad del tiempo de O(2*n) a O(n) mientras que la complejidad del espacio permanece igual.
Implementación:
C++
// CPP program to find first repeated word in a string. #include <bits/stdc++.h> using namespace std; void solve(string s) { int n = s.size(); // size of the string. unordered_map<string, int> mp; // To store first occurance of a word. string ans = "", t = ""; int min_idx = INT_MAX; // To get minimum occurance in // the given string. int i = 0, j = 0; // iterators. i -> initial index of a word // j -> final index of a word. // loop to traverse in a string and to find out each // repeated word whose occurance is minimum. while (j <= n) { // If found an entire word then check if it is // repeated or not using unordered_map. if (s[j] == ' ' || j == n) { if (mp[t] == 0) { // Store the first occurance // of a word. mp[t] = i + 1; } else { // If there is a Repetition then check // for minimum occurance of the word. if (min_idx > mp[t]) { min_idx = mp[t]; ans = t; } } // Shift the pointers. t = ""; i = j + 1; j = i; } else { t += s[j]; j++; } } // If ans is of empty string then this signifies that // there is no Repetition. if (ans == "") cout << "No Repetition" << endl; else cout << ans << endl; } int main() { string s1 = "Ravi had been saying that he had been there"; string s2 = "Ravi had been saying that"; string s3 = "he had had he"; solve(s1); solve(s2); solve(s3); return 0; }
had No Repetition he
Enfoque optimizado:
En lugar de contar un número de ocurrencias de cada palabra que tendrá una complejidad de tiempo y espacio O(N), donde N es el número de palabras, podemos detenernos cuando el conteo de cualquier palabra sea 2. No es necesario iterar a través de todos los palabras en string.
Digamos que nuestra primera palabra repetida está presente en el índice Mth, luego
Al usar este enfoque, la complejidad del espacio y el tiempo se redujo de O(N) a O(M).
Dónde,
N: número de palabras en una string.
M: índice en el que está presente la primera palabra repetida
Sin embargo, en el peor de los casos (cuando no se repite ninguna palabra o la palabra que se repite está presente por última vez), la complejidad de tiempo y espacio seguirá siendo O (N).
Pasos:
- Cree un diccionario predeterminado con un valor inicial de 0, para realizar un seguimiento del recuento de palabras.
- Repita cada palabra en una oración e incremente el conteo de esa palabra en 1.
- Si (recuento de la palabra) > 1, devuelve la palabra.
- Si el recuento de ninguna de las palabras es mayor que 1, entonces estamos fuera de nuestro ciclo y luego devolvemos «No se repite ninguna palabra».
Implementación:
Python3
# Import defaultdict from Collections module from collections import defaultdict def first_repeating_word(s): # Creating a defaultdict with # default values as 0. # Every word will have an # initial count of 0 word_count = defaultdict(lambda: 0) # Iterating through all words in string. for i in s.split(): # Increment the word count of # the word we encounter by 1 word_count[i] += 1 # If word_count of current word # is more than 1, we got our answer, return it. if word_count[i] > 1: return i # If program has reached here that # means no word is being repeated return 'No word is being repeated' # Driver Code if __name__ == '__main__': s = "Ravi had been saying that he had been there" print(first_repeating_word(s)) # This code is contributed by Anurag Mishra
Javascript
<script> function first_repeating_word(s){ // Creating a defaultdict with // default values as 0. // Every word will have an // initial count of 0 let word_count = new Map() // Iterating through all words in string. for(let i of s.split(' ')){ // Increment the word count of // the word we encounter by 1 if(word_count.has(i)){ word_count.set(i,word_count.get(i) + 1); } else word_count.set(i,1); // If word_count of current word // is more than 1, we got our answer, return it. if(word_count.get(i) > 1) return i } // If program has reached here that // means no word is being repeated return 'No word is being repeated' } // Driver Code let s = "Ravi had been saying that he had been there" document.write(first_repeating_word(s)) // This code is contributed by shinjanpatra </script>
had
Complejidad temporal: O(M)
Complejidad espacial: O(M)
Enfoque optimizado 2:
En lugar de contar un número de ocurrencias de cada palabra que tendrá una complejidad de tiempo y espacio O(N), donde N es un número de palabras, podemos simplemente almacenar palabras en un HashSet, y tan pronto como lleguemos a una palabra que ya está presente en el HashSet que podemos devolver.
Implementación:
C++
// CPP program for finding first repeated // word in a string #include <bits/stdc++.h> using namespace std; // returns first repeated word string findFirstRepeated(string s) { // break string into tokens // and then each string into set // if a word appeared before appears // again, return the word and break istringstream iss(s); string token; // hashset for storing word and its count // in sentence set<string> setOfWords; // store all the words of string // and the count of word in hashset while (getline(iss, token, ' ')) { // if word exists return if (setOfWords.find(token) != setOfWords.end()) { return token; } // insert new word to set setOfWords.insert(token); } return "NoRepetition"; } // driver program int main() { string s("Ravi had been saying that he had been there"); string firstWord = findFirstRepeated(s); if (firstWord != "NoRepetition") cout << "First repeated word :: " << firstWord << endl; else cout << "No Repetitionn"; return 0; }
Java
// Java program for finding first repeated // word in a string import java.util.*; public class GFG{ // returns first repeated word static String findFirstRepeated(String s) { // break string into tokens String token[] = s.split(" "); // hashset for storing words HashSet<String> set = new HashSet<String>(); // store the words of string in hashset for(int i=0; i<token.length; i++){ // if word exists return if(set.contains(token[i])){ return token[i]; } // insert new word to set set.add(token[i]); } return "NoRepetition"; } // driver program public static void main(String args[]) { String s = "Ravi had been saying that he had been there"; String firstWord = findFirstRepeated(s); if (!firstWord.equals("NoRepetition")) System.out.println("First repeated word :: " + firstWord); else System.out.println("No Repetitionn"); } }
Javascript
// javascript program for finding first repeated // word in a string class GFG { // returns first repeated word static findFirstRepeated(s) { // break string into tokens var token = s.split(" "); // set for storing words var set = new Set(); // store the words of string in set for (let i=0; i < token.length; i++) { // if word exists return if (set.has(token[i])) { return token[i]; } // insert new word to set set.add(token[i]); } return "NoRepetition"; } // driver program static main(args) { var s = "Ravi had been saying that he had been there"; var firstWord = GFG.findFirstRepeated(s); if (firstWord !== "NoRepetition") { console.log("First repeated word :: " + firstWord); } else { console.log("No Repetitionn"); } } } GFG.main([]); # This code is contributed by mukulsomukesh
First repeated word::had
Este artículo es una contribución de Aarti_Rathi y Mandeep Singh . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA