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

Problem :  Write a Java programme to impress the duplicate words from a given controversy e.g. if given String is "Java in addition to JavaScript are totally different, JavaScript follows Java" in addition to so your programme should impress "Java" in addition to "JavaScript" because those 2 are 2 duplicate words from given String. You demand to consider all cases e.g. given String tin locomote null, empty, may or may non incorporate whatever duplicate words, but for simplicity, you lot tin assume that judgement volition ever inward English linguistic communication in addition to alone utilization ASCII characters, alphabets, in addition to numerals, no special character.  It's meliorate to larn the requirement correct of the work inward the starting fourth dimension fifty-fifty if the interviewer doesn't nation you lot everything. Directly jumping into solution without shout out for a twain 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 guide hold a appear at Cracking the Coding Interview book. It contains 150 Programming Questions in addition to their Solutions, which is expert plenty to clear most of the beginner in addition to intermediate programming project interviews.

Solution : In social club to abide by duplicate words, nosotros foremost demand to dissever the judgement into words. For that, you lot tin split the String on infinite using a greedy regular expression, so that it tin grip multiple white spaces betwixt words. You tin utilization the split() method of java.lang.String shape to produce that, this method returns an array of words.

Once nosotros listing of words, nosotros tin insert them into HashSet. Since HashSet doesn't permit duplicate in addition to its add() method render imitation if an object already exists inward HashSet, nosotros tin abide by all duplicate words. Just loop over array, insert them into HashSet using add() method, banking firm gibe output of add() method. If add() returns imitation in addition to so it's a duplicate, impress that give-and-take to the console.

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

One of the follow-up questions of this is how produce you lot abide by a publish of times each duplicate give-and-take has appeared inward a sentence? For example, inward our coding problem, your solution should besides impress count of both Java in addition to JavaScript e.g. Java : 2 in addition to JavaScript : 2 because they guide hold appeared twice inward a sentence.

You tin solve this work yesteryear choosing simply 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, in addition to ConcurrentHashMap, but for full general purpose, HashMap is expert enough.

In short, simply utilization HashMap instead of HashSet to decease on count of duplicate words inward the sentence. This is besides similar to the work of finding duplicate characters inward String. Instead of character, you lot demand to abide by duplicate words, every bit shown here.

Another follow-up inquiry related to this work is how produce you lot take away duplicate words from String inward Java? Which is truly the same work 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 upwards whatever problem,  see this solution.

Java Program to abide by duplicate words inward String

Here is our solution to the work of finding duplicate words inward a judgement inward Java. I guide hold used HashSet to abide by duplicates. The fourth dimension complexity of this solution is O(n) because nosotros demand to iterate over all chemical factor inward 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 locomote suitable for a truly long String. You demand to a greater extent than retention to abide by fifty-fifty a unmarried duplicate give-and-take if your String is huge.

import java.util.Collections; import java.util.HashSet; import java.util.Set;  /**  * Java Program to demonstrate how to abide by duplicate words inward String.  */ public class DuplicateWordsInString{      public static void main(String[] args) {         String test = "This judgement contains 2 words, ane in addition to two";         Set<String> duplicates = duplicateWords(test);         System.out.println("input : " + test);         System.out.println("output : " + duplicates);     }       /**      * Method to abide by duplicate words inward 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 give-and-take : 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 programme is working every bit expected, It correct prints that "two" is the alone duplicate give-and-take inward given String. Nonetheless, nosotros are going to write simply about unit of measurement bear witness to farther bear witness our solution for dissimilar input values.

JUnit tests

Here is my listing of JUnit bear witness shape for our solution. We are going to bear witness our solution for empty String, goose egg String, String amongst alone duplicates, String without whatever duplicates in addition to String which contains multiple spaces betwixt words.  Each JUnit tests ane input. If your input laid is large in addition to so 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 near how to abide by duplicate words inward a given String inward Java. We guide hold used HashSet information construction to solve this work in addition to our solution has fourth dimension in addition to infinite complexity of O(n). For a curious developer, tin you lot come upwards up amongst a solution amongst meliorate fourth dimension in addition to infinite complexity? How near a solution amongst fourth dimension complexity inward social club of O(k) where k is duplicate words? or O(logN)?

Further Learning
The Coding Interview Bootcamp: Algorithms + Data Structures
Data Structures in addition to Algorithms: Deep Dive Using Java
Algorithms in addition to Data Structures - Part 1 in addition to 2

Sumber https://javarevisited.blogspot.com/

Share this post