How To Detect Duplicate Words Inwards Coffee String? [Solution]

Baca Juga

Problem :  Write a Java computer program to impress the duplicate words from a given tilt e.g. if given String is "Java together with JavaScript are totally different, JavaScript follows Java" together with then your computer program should impress "Java" together with "JavaScript" because those 2 are 2 duplicate words from given String. You demand to consider all cases e.g. given String tin live on null, empty, may or may non comprise whatever duplicate words, but for simplicity, you lot tin assume that judgement volition ever inwards English linguistic communication together with solely utilization ASCII characters, alphabets, together with numerals, no special character.  It's improve to larn the requirement correct of the occupation inwards the start fifty-fifty if the interviewer doesn't nation you lot everything. Directly jumping into solution without scream for a duet of questions may non become good amongst many interviewers who looks for exceptional oriented candidates.

If you lot are practicing these coding problems for an interview, I besides advise you lot accept a seem at Cracking the Coding Interview book. It contains 150 Programming Questions together with their Solutions, which is practiced plenty to clear most of the beginner together with intermediate programming undertaking interviews.

Solution : In lodge to honour duplicate words, nosotros firstly demand to split upward the judgement into words. For that, you lot tin split the String on infinite using a greedy regular expression, so that it tin lead hold multiple white spaces betwixt words. You tin utilization the split() method of java.lang.String aeroplane to create that, this method returns an array of words.

Once nosotros listing of words, nosotros tin insert them into HashSet. Since HashSet doesn't let duplicate together with its add() method render fake if an object already exists inwards HashSet, nosotros tin honour all duplicate words. Just loop over array, insert them into HashSet using add() method, cheque output of add() method. If add() returns fake together with then it's a duplicate, impress that discussion to the console.

This is besides ane of the top twenty String based problems from interviews. You tin run into that article to to a greater extent than coding problems based upon String.

One of the follow-up questions of this is how create you lot honour a seat out of times each duplicate discussion has appeared inwards a sentence? For example, inwards our coding problem, your solution should besides impress count of both Java together with JavaScript e.g. Java : 2 together with JavaScript : 2 because they receive got appeared twice inwards a sentence.

You tin solve this occupation past times choosing merely about other hash-based information construction similar a hash table, which maintains fundamental value pair. Java provides several implementation of hash tabular array information construction e.g. HashMap, Hashtable, together with ConcurrentHashMap, but for full general purpose, HashMap is practiced enough.

In short, merely utilization HashMap instead of HashSet to continue count of duplicate words inwards the sentence. This is besides similar to the occupation of finding duplicate characters inwards String. Instead of character, you lot demand to honour duplicate words, every bit shown here.

Another follow-up inquiry related to this occupation is how create you lot withdraw duplicate words from String inwards Java? Which is genuinely the same occupation of removing duplicate elements from an array? If you lot know how to solve that, you lot tin easily solve this ane every bit well. If you lot human face upward whatever problem,  see this solution.

Java Program to honour duplicate words inwards String

Here is our solution to the occupation of finding duplicate words inwards a judgement inwards Java. I receive got used HashSet to honour duplicates. The fourth dimension complexity of this solution is O(n) because nosotros demand to iterate over all chemical component inwards the array. You besides demand a buffer of the same size every bit master copy array, hence, the infinite complexity is besides O(n), so it may non live on suitable for a genuinely long String. You demand to a greater extent than retentiveness to honour fifty-fifty a unmarried duplicate discussion if your String is huge.

import java.util.Collections; import java.util.HashSet; import java.util.Set;  /**  * Java Program to demonstrate how to honour duplicate words inwards String.  */ public class DuplicateWordsInString{      public static void main(String[] args) {         String test = "This judgement contains 2 words, ane together with two";         Set<String> duplicates = duplicateWords(test);         System.out.println("input : " + test);         System.out.println("output : " + duplicates);     }       /**      * Method to honour duplicate words inwards a Sentence or String      * @param input String       * @return laid of duplicate words      */     public static Set<String> duplicateWords(String input){                  if(input == null || input.isEmpty()){             return Collections.emptySet();         }         Set<String> duplicates = new HashSet<>();                  String[] words = input.split("\\s+");         Set<String> set = new HashSet<>();                  for(String discussion : words){             if(!set.add(word)){                 duplicates.add(word);             }         }         return duplicates;     }           }  Output : input : This judgement contains 2 words, ane and 2 output : [two] 

From the output it's clear that our computer program is working every bit expected, It correct prints that "two" is the solely duplicate discussion inwards given String. Nonetheless, nosotros are going to write merely about unit of measurement examine to farther examine our solution for dissimilar input values.

JUnit tests

Here is my listing of JUnit examine aeroplane for our solution. We are going to examine our solution for empty String, goose egg String, String amongst solely duplicates, String without whatever duplicates together with String which contains multiple spaces betwixt words.  Each JUnit tests ane input. If your input laid is large together with then you lot tin besides consider using parameterized JUnit test.

import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertTrue;  import java.util.Collections; import java.util.Set;  import org.junit.Test;  public class DuplicateWordsInStringTest {             @Test     public void testWithEmptyString(){                 Set<String> output = DuplicateWordsInString.duplicateWords("");         assertEquals(Collections.emptySet(), output);     }          @Test     public void testWithNullString(){         Set<String> output = DuplicateWordsInString.duplicateWords(null);         assertEquals(Collections.emptySet(), output);     }          @Test     public void testWithDuplicateString(){         Set<String> output = DuplicateWordsInString.duplicateWords("one ane one 2 two");         assertTrue(output.contains("one"));         assertTrue(output.contains("two"));         assertTrue(output.size() == 2);     }          @Test     public void testWithOutDuplicates(){         Set<String> output = DuplicateWordsInString.duplicateWords("one 2 three");         assertEquals(Collections.emptySet(), output);     }          @Test     public void testWithMultipleSpaceBetweenWord(){         Set<String> output = DuplicateWordsInString.duplicateWords(" ane   2    iii ");         assertEquals(Collections.emptySet(), output);     }           }

That's all most how to honour duplicate words inwards a given String inwards Java. We receive got used HashSet information construction to solve this occupation together with our solution has fourth dimension together with infinite complexity of O(n). For a curious developer, tin you lot come upward up amongst a solution amongst improve fourth dimension together with infinite complexity? How most a solution amongst fourth dimension complexity inwards lodge of O(k) where k is duplicate words? or O(logN)?

Further Learning
The Coding Interview Bootcamp: Algorithms + Data Structures
Data Structures together with Algorithms: Deep Dive Using Java
Algorithms together with Data Structures - Part 1 together with 2