Anagram
Two strings are called anagrams if they contain same set of characters but in different order. For example,
-
peek and keep are anagrams
-
spar and rasp are anagrams
-
listen and silent are anagrams
For more info:
Create anagram buckets from a given input array of words
Upasana | May 18, 2019 | 2 min read | 156 views | Java Coding Challenges
Here we get an input array of words that contains anagram string, and we need to create buckets for all the anagrams words.
Input:
{"akka", "akak", "baab", "baba", "bbaa"}
Output:
{
[akka, akak],
[baab, baba, bbaa]
}
Approach
-
Create a hashmap that will hold sorted word as the key and list of anagrams as the value. We will use this hashmap to store the results.
-
For each word in the input array, create a key by sorting the characters and put this word to that list whose key is the sorted word. for example [aakk → akka, akak] If it does not exist then create a new list with the sorted word as key in map.
-
In the end, traverse the values of hashmap and we get the desired result.
Java Implementation
Anagrams.java
import java.util.*;
public class Anagrams {
public static void main(String[] args) {
String[] input = {"akka", "akak", "baab", "baba", "bbaa"};
Map<String, List<String>> anagramsMap = anagramBuckets(input);
System.out.println("anagramsMap = " + anagramsMap);
}
private static Map<String, List<String>> anagramBuckets(String[] input) {
Map<String, List<String>> anagramsMap = new HashMap<>(100);
for (String s : input) {
char[] word = s.toCharArray();
Arrays.sort(word);
String key = String.valueOf(word);
if (!anagramsMap.containsKey(key)) {
anagramsMap.put(key, new ArrayList<>());
}
anagramsMap.get(key).add(s);
}
return anagramsMap;
}
}Time Complexity
If we ignore the time consumed by sorting an individual string then we can say that the above approach takes Big O(n) time complexity.
Otherwise the actual time complexity would be O (n log n) (for sorting) + O (n) (for compare)
Related article
Java Coding Challenges:
- Reverse position of words in a string using recursion
- Check if the given string is palindrome
- Find two numbers of which the product is maximum in an array
- Prime number checker in Java
- Anagrams string checker in Java
- Reverse a string using recursion in Java
- Java Program to find Factorial of a number
Top articles in this category:
- Get distinct words from a given file in Java
- Reverse order of words inside string in Java
- Anagrams string checker in Java
- Reverse position of words in a string using recursion
- Find longest non-repeating substring from a given string in Java
- Java Coding Problems for SDET Automation Engineer
- Find two numbers of which the product is maximum in an array
Recommended books for interview preparation:
Book you may be interested in..
Book you may be interested in..
