Count occurrence of multiple substrings

Question

I want to count the occurrence of multiple substrings in a string. I am able to do so by using the following code:

int score = 0;
String text = "This is some random text. This is some random text.";
List<String> words = Arrays.asList("this", "is", "for", "stackoverflow");
for (String word : words) {
    if(StringUtils.containsIgnoreCase(text, word)){
        score += 1;
    }
}

My algorithm increases the score by +1 for each word from my "words" list that occurs in the text. In my example, the score would be 2 because "this" and "is" occur in the text.

However, my code has to loop through the text for each string in my list. Is there a faster way to do this?

Why not using countMatches() for every word in your list ? — Tom
– Tom, Commented Mar 18, 2022 at 13:03
In my example, the score would be 2 because "this" and "is" occur in the text Wouldn't the score be 4 since both This and is occur twice in the text? — Abra
– Abra, Commented Mar 18, 2022 at 13:19

Abra · Accepted Answer · 2022-03-18 13:29:47Z

1

How about the following:

String text = "This is some random text. This is some random text.";
text = text.toLowerCase();
String[] tokens = text.split("\\PL+");
java.util.Set<String> source = new java.util.HashSet<>();
for (String token : tokens) {
    source.add(token);
}
java.util.List<String> words = java.util.Arrays.asList("this", "is", "for", "stackoverflow");
source.retainAll(words);
int score = source.size();

Split text into words.
Add the words to a Set so that each word appears only once. Hence Set will contain the word this only once despite the fact that the word this appears twice in text.
After calling method retainAll, the Set only contains words that are in the words list. Hence your score is the number of elements in the Set.

answered Mar 18, 2022 at 13:29

Abra

21k14 gold badges100 silver badges74 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

EustassX Over a year ago

Thanks, that worked! Is there a way to do the same thing, but also check if the word is included in the token?

NoMoreThan10IQ · Accepted Answer · 2022-03-18 13:08:41Z

0

The fastest way would be to map each words of the text.

Therefore for each word in the words that you are searching for, you just have to look up for the keys in the hashmap.

Given your text has n word and your words has m words The solution would take O(n+m) instead of O(n*m)

answered Mar 18, 2022 at 13:08

NoMoreThan10IQ

11 bronze badge

Comments

Ryan · Accepted Answer · 2022-03-18 14:19:37Z

This is a case where regex is your friend:

public static Map<String, Integer> countTokens(String src, List<String> tokens) {
    Map<String, Integer> countMap = new HashMap<>();
    String end = "(\\s|$)"; //trap whitespace or the end of the string.
    String start = "(^|\\s)"; //trap for whitespace or the start of a the string
    //iterate through your tokens
    for (String token : tokens) {
        //create a pattern, note the case insensitive flag
        Pattern pattern = Pattern.compile(start+token+end, Pattern.CASE_INSENSITIVE);
        Matcher matcher = pattern.matcher(src);
        int cnt = 0;
        //count your matches.
        while(matcher.find()) {
            cnt++;
        }
        
        countMap.put(token, cnt);
    }
    
    return countMap;
}


public static void main(String[] args) throws IOException {
    String text = "This is some random text. This is some random text.";
    List<String> words = Arrays.asList("this", "is", "for", "stackoverflow");
    
    for (Entry<String, Integer> entry : countTokens(text, words).entrySet()) {
        System.out.println(entry);
    }
}

If you want to find tokens within token, like "is" within "this", simply remove the start and end regex.

Hiten Tandon · Accepted Answer · 2022-03-18 15:51:51Z

You can use split method, to convert string to Array of Strings, sort it, and then you can binary search the elements of list in the array this has been implemented in the given code.

String[] wordsArr =  "This is some random text. This is some random text.".toLowerCase().split(" ");
List<String> words = Arrays.asList("this", "is", "for", "stackoverflow");
int count = 0;
Arrays.sort(wordsArr);
for(String word: words)
    if(Arrays.binarySearch( wordsArr, word )>-1)
         count++;

Another good approach can be to use a TreeSet, this one I got inspiration from @Abra

String[] wordsArr =  "This is some random text. This is some random text.".toLowerCase().split(" ");
List<String> words = Arrays.asList("this", "is", "for", "stackoverflow");
TreeSet<String> setOfWords = new TreeSet<String>(Arrays.asList(wordsArr));
int count = 0;
for(String word: words)
    if(setOfWord.contains(word))
        count++;

Both these methods have a Time Complexity of O(Nlog(M)), N being the size of words array, M being the size of wordsArr or setOfWords, However do be careful, using this method since this does have one flaw, which is quite obvious, It doesn't account for periods, thus, if you were to search for "text", it won't be found, because, The set/array contains "text.". You can get around that by removing all the punctuations from your initial text and searched text, however, if you do want it to be accurate then, you can set the regex string in split() to be "[^a-zA-Z]" this will split your String around non alphabetical characters.

Collectives™ on Stack Overflow

Count occurrence of multiple substrings

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related