查找字符串中第一个重复的单词-yiteyi-C++库

给定一个字符串，找出字符串中第一个重复的单词例如：

null

Input : "Ravi had been saying that he had been there"Output : hadInput : "Ravi had been saying that"Output : No RepetitionInput : "he had had he"Output : he

问题来源： https://www.geeksforgeeks.org/goldman-sachs-interview-experience-set-29-internship/

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

简单方法： 从后面开始迭代，对于每个新词，将其存储在无序地图中。对于每个出现不止一个的单词，更新ans为该单词，最后反转ans并打印。

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 occurences 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<<                                     ''                                     ;                       
                                                 }                       
                                                 else                       
                                                 cout<<                                     "No Repetition"                                     ;                       
                         }                       
                         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;                       
                                   
                         }                       

Javascript

                         <script>                       
                         // JavaScript program to find first repeated word in a string                       
           
                         function                                     solve(s)                       
                         {                       
                                                 let mp =                                     new                                     Map();                                     // to store occurences 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>                       

输出

hadNo Repetitionhe

另一种方法： 其思想是对字符串进行标记，并将每个单词及其计数存储在hashmap中。然后再次遍历字符串，并在创建的hashmap中检查字符串的每个单词的计数。

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"                                     );                       
                                                 }                       
                         }                       

输出

First repeated word :: had

方法#2：使用内置python函数：

因为一个句子中的所有单词都用空格隔开。
我们必须用空格分隔句子 split（）。
我们将所有单词按空格分割，并将它们存储在一个列表中。
使用柜台函数计算单词的频率
遍历列表并检查是否有任何单词的频率大于1
如果存在，则打印单词并打破循环

以下是实施情况：

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):                       
           
                                                 # spliting 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

优化方法：

我们可以在任何单词的计数变为2时停止计算，而不是计算每个单词出现的次数，这些单词的时间和空间复杂度为O（N），其中N是单词数。这不需要遍历字符串中的所有单词。

假设我们的第一个重复单词出现在Mth索引中

通过使用这种方法，空间和时间复杂度从O（N）降低到O（M）。

哪里

N：字符串中的字数。

M：出现第一个重复单词的索引

然而，在最坏的情况下（当没有单词被重复或被重复的单词最终出现时），时间和空间复杂度仍然是O（N）。

步骤：

创建一个默认字典初始值为0，以跟踪字数。
重复一个句子中的每个单词，并将该单词的计数增加1。
如果（单词计数）>1，则返回单词。
如果所有单词的计数都不大于1，则表示我们在循环之外，然后返回“没有单词被重复”。

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                       

输出

had

时间复杂度：O（M）

空间复杂度：O（M）

优化方法2：

我们不需要计算每个单词的出现次数，因为每个单词的时间和空间复杂度都是O（N），其中N是单词的数量，我们只需要将单词存储在哈希集中，一旦我们找到哈希集中已经存在的单词，我们就可以返回。

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"                                     );                       
                                                 }                       
                         }                       

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;                       
                         }                       

输出

First repeated word :: had

本文由 曼迪星 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章