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
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
-
Anoop Kumaruse Set .
make all different sets and compare with elements -
rahul69Well 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. 😎 -
ankur8819I 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
al= new ArrayList (); ArrayList groupList= new ArrayList(); ArrayList finalList= new ArrayList(); for(int i=0;i -
simplycoderYour 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. -
surazwhy not join nataraz.blogspot.com where we are uploading all standard question daily
You are reading an archived discussion.
Related Posts
Internet hackers group Anonymous has finally landed in India. Here is an interesting chat of a reporter with the group.
https://nh7.in/indiecision/2012/05/26/nh7-chat-anonymous/
Now the issue is, do we really need them...
Has anyone here have any experience on PCB Design Fab Assembly start
up?
May I know how did it go?
What are the considerations?
What are the challenges involved?
Google plans to warn more than half a million users of a computer infection that may knock their computers off the Internet this summer.
Hackers have infected a network of...
Name:gwendollen
*Engineering Trade:ECE
Location:ANDHRA PRADESH
*Occupation: i am a B-Tech final year student
*Hobbies & Interests: surfing the net,reading detective and adventourous stories and playing chess
For those who have tried getting online quotes from PCB vendors (i.e. for design or fabrication),
may I know your feedback from doing this?
I personally have not tried sending...