2
\$\begingroup\$

The assignment is to remove the repeating string from a given string and get the count of repeated string.

The code I have tried is below :

public static void main(String[] args) {

        String longString = "Energy in the form of seismic waves is released " +
                            "after an earthquake and seismometers measure its amplitude to calculate the " +
                            "quake's intensity. For a long time, earthquakes were measured on the Richter scale." +
                            " Since the scale was based on conditions in California and was not reliable in measuring large earthquakes," +
                            " it was replaced by a 'moment magnitude' scale in the 1970s";



        // replace the special characters
        String freeString = longString.replaceAll("[^\\w\\s-]", "");
        //the new string is  
        System.out.println("freeString ::  " + freeString);
        //Calculate the length of the string
        String[] countOfString = freeString.split(" ");

        System.out.println("countOfString  ::  " + countOfString.length);

        Set<String> uniqueString = new HashSet<String>();
        Map<String, Integer> countMap = new HashMap<String, Integer>();
        for (int i = 0; i < countOfString.length; i++) {
            String tempString = countOfString[i];
            if(!uniqueString.contains(tempString)){
                uniqueString.add(tempString);
            }else{
                if(!countMap.containsKey(tempString)){
                    countMap.put(tempString, 1);
                }else{
                    Integer count = countMap.get(tempString);
                    count++;
                    countMap.put(tempString, count);
                }

                System.out.println("found the repeating string " + tempString);
            }
        }

        //remove the repeating string set from the uniqueString set 
        uniqueString.removeAll(countMap.keySet());
        System.out.println("the repeating string " + countMap);
        System.out.println("the set has the uniuqe strings " + uniqueString);
        System.out.println("the set has the uniuqe strings of length " + uniqueString.size());

    }

Is there any best way/approach other than this? Will this code work for very large string (e.g. parsing the text of a book) Will it have any performance issue?

\$\endgroup\$
3
  • \$\begingroup\$ What do you mean exactly by "repeating strings"? only single words, or the same set of consecutive words (whatever the punctuation), an other thing? \$\endgroup\$ Apr 29, 2015 at 12:17
  • \$\begingroup\$ @CasimiretHippolyte : single word \$\endgroup\$ Apr 29, 2015 at 12:18
  • \$\begingroup\$ Ok, that is already more simple. \$\endgroup\$ Apr 29, 2015 at 12:21

2 Answers 2

2
\$\begingroup\$

Your algorithm seems fine. It doesn't reveal any special tricks to me, but I also don't see any unnecessary steps. I think I'd have written it myself that way. The only part that I might have done differently is the regex; I'm not sure that one is fully correct.

So on an algorithmic level you're doing perfectly fine. However, the implementation suffers from spelling issues.

Comments

First, you have some comments.

    // replace the special characters
    String freeString = longString.replaceAll("[^\\w\\s-]", "");
    //the new string is  
    System.out.println("freeString ::  " + freeString);
    //Calculate the length of the string
    String[] countOfString = freeString.split(" ");

Comments are nice, they help understand what's going on... but so does the code. Of course replaceAll replaces things, we already know that the new string is the freeString, and that String.split calculates the length of the string is actually not what it does.

You should replace your comments with comments with non-obvious things about what the code does (What does your regex actually do?), or comments about why the code does.

Variable Naming

Variable naming should be based on what the variable stores - usually its "semantic type". A "syntactic type" would be a String, Integer and so on. The "semantic type" is what it means - "inputString", "validatedString", "splittedString", "stringsToLoopThrough"... some of these are better than others. A semantic type doesn't have to include the syntactic type - you can have variable names like "index", "key", "value", without containing any notion of syntactic type. Usually the syntactic type is inferred, and at other times, it doesn't matter what the type is, just that it's the index/key/value/whatever.

Based on that, I think you should name countOfString words, uniqueString uniqueWords, countMap wordCountMap, and countString cleanedLongString.

countOfString seems to indicate a number. But it's a string array instead. A string array containing the words of the longString. So words seems like a fitting name. It certainly seems logical that if you split a longString on a space, you will get words.

uniqueString to uniqueWords is because of two reasons. First, by changing to Words, we signal that this variable is related to the words variable. Second, by pluralizing the variable name from String to Strings (or Word -> Words), we say this is a "collection" of sorts. Something which holds multiple values.

countMap to wordCountMap is to signal the relationship with words.

countString to cleanedLongString has two reasons, first to again note a relationship with another variable, this time with longString. Second, I add the cleaned because you have cleaned the special characters out of the original string.

The names aren't ideal yet - longString seems like a bad name, considering it doesn't have to be a longString, and it doesn't signal that it needs to be cleaned first.

\$\endgroup\$
2
\$\begingroup\$

Your data structures are fine. However, if you want to scale up to handle, say, a book, you will want to avoid longString.replaceAll(…) and freeString.split(" "). For that matter, you don't want to ever assemble all of the input in one long string in the first place. The solution to that scalability problem is to use a Scanner.

Putting all the code in one main() function limits the reusability of this code.

You should be able to avoid all .containsKey() and .contains() checks. Also, the fact that countMap keeps track of the repeat count (which is one less than the occurrence count) is deceptive — it's worth better naming and a very explicit comment.

The handling of intra-word punctuation is, in my opinion, wrong. By purging all special characters as your first processing step, you end up treating quake's as quakes. Proper treatment of apostrophes and hyphens that still discards single quotes and dashes is tricky.

import java.util.*;
import java.util.regex.Pattern;

public class WordDeduplicator {
    private static final Pattern NOISE = Pattern.compile(
        // punctuation that is not apostrophe or hyphen
        "((?!(?<=\\w)['-](?=\\w))\\W)+"
    );

    private int wordCount;
    private HashMap<String, Integer> words = new HashMap<>(),
                                     repeat = new HashMap<>();
    private Set<String> unique = new HashSet<>();

    public WordDeduplicator(Scanner source) {
        source.useDelimiter(NOISE);
        for (wordCount = 0; source.hasNext(); wordCount++) {
            String word = source.next();
            Integer thisWordCount = words.put(word, 1);
            if (thisWordCount == null) {                // First occurrence
                unique.add(word);
            } else {
                if (thisWordCount == 1) {               // Second occurrence
                    unique.remove(word);
                }
                repeat.put(word, thisWordCount);        // Second or subsequent
                words.put(word, 1 + thisWordCount);
            }
        }
    }

    public int getWordCount() {
        return this.wordCount;
    }

    public Map<String, Integer> getDistinctWords() {
        return Collections.unmodifiableMap(this.words);
    }

    /**
     * Returns the words that appear more than once, and their
     * repeat count (i.e., one less than the number of occurrences).
     */
    public Map<String, Integer> getRepeatedWords() {
        return Collections.unmodifiableMap(this.repeat);
    }

    public Set<String> getUniqueWords() {
        return Collections.unmodifiableSet(this.unique);
    }

    public static void main(String[] args) {
        String longString = "Energy in the form of seismic waves is released " +
        "after an earthquake and seismometers measure its amplitude to calculate the " +
        "quake's intensity. For a long time, earthquakes were measured on the Richter scale." +
        " Since the scale was based on conditions in California and was not reliable in measuring large earthquakes," +
        " it was replaced by a 'moment magnitude' scale in the 1970s";

        WordDeduplicator wd = new WordDeduplicator(new Scanner(longString));
        System.out.println(wd.getWordCount());
        System.out.println("Repeated strings " + wd.getRepeatedWords());
        System.out.println("The set has the unique strings " + wd.getUniqueWords());
        System.out.println(wd.getUniqueWords().size());
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.