Grouping similar strings in a String array in Java

ankur8819
Member • May 26, 2012

Grouping similar strings in a String array in Java

Hi,
I am working on a problem wherein I need to Group similar strings in an Array.
i.e If my String array is say "AXPZ","BXT","PZXA","XAZP","XBT","TBX","ABCD"
then I would group AXPZ,PZXA and XAZP in one group.
BXT,XBT and TBX in 2nd group
ABCD in 3rd group.
A group consists of String having same characters (order does not matter)
1)What would be the best approach for the problem.
2) What would be the final DataStructure representing groups and Simillar Strings.
3)What should be the approach for this problem.

If anyone has worked on similar problem do provide some comments or ways to approach it.

Regards,
Ankur Luthra

Replies

Howdy guest!

Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.

Replies

Anoop Kumar

Member • May 26, 2012

use Set .
make all different sets and compare with elements

Are you sure? This action cannot be undone.
Cancel
rahul69

Member • May 26, 2012

Well in my opinion, you can start with partial groups and move towards more perfect grouping.
First divide on the basis of string length.
Then in each group:
match first string letters with rest of the strings (increment the flag if a letter is found anywhere in
string), so that all letters are matched.
those strings which are not matched are put in new group and matching check is repeated again,
until:
only one string remains in the group.
Thus the groups are created.
I don't know whether this is the best possible solution or not but hope this helps. 😎

Are you sure? This action cannot be undone.
Cancel

ankur8819

Member • May 26, 2012

I was able to do it in following way.Any comments to improve the performance if the String array length is say 10000.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
 
 
public class SimilarStrings {
 
    public static void main(String[] args) {
   
        String s[]= new String[]{"AXP","PXA","ABCD","XPA","TYPZ","YTPZ","DESP","PDSE","XAP","ZYTP","BACD","DACB"};
        ModifiedString md= null;
        ArrayList<ModifiedString> al= new ArrayList<ModifiedString>();
        ArrayList groupList= new ArrayList();
        ArrayList finalList= new ArrayList();
        for(int i=0;i<s.length;i++)
        {
            md=new ModifiedString();
            md.setOriginalString(s[i]);
            md.setSortedString(md.createSortedString(s[i]));
            al.add(md);
        }
       
        Collections.sort(al,new SortedStringComparator());
       
        ModifiedString md1=al.get(0);
        groupList.add(al.get(0).getOriginalString());
        for(int j=1;j<al.size();j++)
        {
            if(md1.getSortedString().equalsIgnoreCase(al.get(j).getSortedString()))
            groupList.add(al.get(j).getOriginalString());
            else{
                finalList.add(groupList);
                groupList= new ArrayList();
                groupList.add(al.get(j).getOriginalString());
                md1=al.get(j);
            }
            if(j==al.size()-1)
                finalList.add(groupList);
           
        }
        System.out.println("FianlList is the Desired Answer");
           
    }
   
}
 
class ModifiedString{
    private String originalString;
    private String sortedString;
    public String getOriginalString() {
        return originalString;
    }
    public void setOriginalString(String originalString) {
        this.originalString = originalString;
    }
    public String getSortedString() {
        return sortedString;
    }
    public void setSortedString(String sortedString) {
        this.sortedString = sortedString;
    }
   
    public String createSortedString(String originalString)
    {
       
        if(null!=originalString)
        {
            char[] content = originalString.toCharArray();
            java.util.Arrays.sort(content);
            return new String(content);
        }
        else
            return "";
    }
}
 
class SortedStringComparator implements Comparator{
 
    @Override
    public int compare(Object arg0, Object arg1) {
        // TODO Auto-generated method stub
        ModifiedString temp1= (ModifiedString)arg0;
        ModifiedString temp2= (ModifiedString)arg1;
        String f= temp1.getSortedString();
        String f1= temp2.getSortedString();
        return f.compareToIgnoreCase(f1);
               
    }
   
   
}

Are you sure? This action cannot be undone.

Cancel

simplycoder

Member • May 29, 2012

Your approach is correct, but instead of sorting each string and then comparing,
store a copy of all strings in another storage,remember the indices and sort them and replace the indices.
then your can gather according to your need al at once.

If you are trying this for optimization, I would suggest you implement some sorting algorithm like radix sort or similar.

Are you sure? This action cannot be undone.
Cancel
suraz

Member • Jun 19, 2012

why not join nataraz.blogspot.com where we are uploading all standard question daily

Are you sure? This action cannot be undone.
Cancel