This post is completed by 6 users

  • 1
 Add to List
Beginner

516. Count similar words in a given array

Given an array of strings, write a program to count all the similar words. 

Similar words: Two words are similar if

  1. Has spaces in-between or at the end. Ex: "Apple" and " A pp le" are similar.
  2. Has upper or lower cases. Ex: "APPle" and "apple" are similar.
  3. Has special characters. Ex: "app%^L&e" and "@@apple" are similar.

Example:;

input = ["Apple", "Bat", "apple", "A%^%ppLE", "BA  T", " C A T", "cAt "]
Output:
apple -- 3
bat -- 2
cat -- 2

Approach: Use Map

Maintain a map which contains the count of each word(word as key and its count as value) and below making an entry into the map do the steps below -

  • Convert the word to lowercase ( to ignore cases).
  • Trim the word from the ends.
  • Remove all the spaces in between.
  • Remove all the special characters.

Once the array is iterated, print the map.

Time Complexity: O(N), Space Complexity: O(N)

 



import java.util.HashMap;
import java.util.Map;

public class Main {

    public static void countWords(String [] input){

        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i <input.length ; i++) {
            String word = input[i];

            //remove spaces if present
            word = word.trim().replace(" ", "");
            //ignore cases
            word = word.toLowerCase();
            //remove if any special character present
            word = word.replaceAll("[^a-zA-Z0-9]", "");

            //insert into map
            if(map.containsKey(word)){
                //increment the count
                int count = map.get(word);
                map.put(word, count+1);
            } else
                map.put(word, 1);

        }
        //print the result
        for(String key:map.keySet()){
            System.out.println(key + " -- " + map.get(key));
        }
    }

    public static void main(String[] args) {
        String [] input = {"Apple", "Bat", "apple", "A%^%ppLE", "BA  T", " C A T", "cAt "};
        countWords(input);
    }
}



def count_words(input):
    word_count = {}
    for word in input:
        # Remove spaces if present
        word = word.strip().replace(" ", "")
        # Ignore cases
        word = word.lower()
        # Remove any special characters
        word = ''.join(e for e in word if e.isalnum())

        # Insert into the dictionary
        if word in word_count:
            # Increment the count
            word_count[word] += 1
        else:
            word_count[word] = 1

    # Print the result
    for word, count in word_count.items():
        print(f"{word} -- {count}")

if __name__ == "__main__":
    input = ["Apple", "Bat", "apple", "A%^%ppLE", "BA  T", " C A T", "cAt "]
    count_words(input)



package main

import (
	"fmt"
	"strings"
	"unicode"
)

func countWords(input []string) {
	wordCount := make(map[string]int)

	for _, word := range input {
		// Remove spaces if present
		word = strings.Replace(word, " ", "", -1)
		// Ignore cases and remove special characters
		word = strings.Map(func(r rune) rune {
			if unicode.IsLetter(r) || unicode.IsNumber(r) {
				return unicode.ToLower(r)
			}
			return -1
		}, word)

		// Insert into the map
		if _, exists := wordCount[word]; exists {
			wordCount[word]++
		} else {
			wordCount[word] = 1
		}
	}

	// Print the result
	for word, count := range wordCount {
		fmt.Printf("%s -- %d", word, count)
		fmt.Println("")
	}
}

func main() {
	input := []string{"Apple", "Bat", "apple", "A%^%ppLE", "BA  T", " C A T", "cAt "}
	countWords(input)
}

Output:

apple -- 3
bat -- 2
cat -- 2

Related Problems: