CODEWITHSUNDEEP
javadata-structures
user2394904
user2394904

Reputation: 71

What data structure should I use to store a pair of strings in Java , if my goal is to find unique pairs?

I am a beginner in Java. I have some sample data of nodes:

A -> B

B -> F

C -> R

A -> B

B -> C

R -> C

I have already taken out 2 lists: [A,B,C,A,B,R] and [B,F,R,B,C,C]

However, how should I go about storing the pairs [AB, BF, CR, AB, BC, RC] so that I can find unique pairs? By unique, I mean AB is not equal to BA .

1) So Basically I would like to identify unique pairs.

2) I also want to count the number of times each unique pair has appeared.

EDITED:

3) I am also interested in finding how many different nodes each node connects to.

4) And how many different nodes connect to each node

I am struggling to decide whether I really need to write my own class or is there an easier method?

Upvotes: 8

Views: 22376

Answers (3)

Kent
Kent

Reputation: 195079

Hashtable (datastructure) should work for your requirement. In java, you could consider type HashMap<String,Integer>

key is the string pair, Integer is count:

something like:

{
"AB":2,
"CR":1,
"BF":1,
...

}

The complexity of finding unique pairs would be O(n)

EDIT

it seems that putting codes here helps to explain the solution:

Map<String, Integer> map = new HashMap<String,Integer>();

//you have two lists with those strings, called list1 and list2.
// list1<String> and list2<String> have same size

String key = null;
for(int i=0;i<list1.size();i++){
    key = list1.get(i) + list2.get(i);
    if(map.containsKey(key))
        map.get(key)++;
    else
        map.put(key,1);
}

//now the map has been filled, you can go through the map, 
//and check the value, if value == 1, then the key is unique.
//for those value >1, you know, which string pair is not unique, 
// and how many times it shows.

codes were not written in IDE, so there could be typoes.

Upvotes: 2

harsh
harsh

Reputation: 7692

You need a class to designate pair:

public class Pair{
 String prv;
 String next;
 //override hashcode and equals
}

If you use Set and fill it in with all pair, you'll end-up having unique pairs:

Set<Pair> pairs = new HashSet<Pair>();
..
pairs.add(new Pair(prv, next));
int uniquePairs = pairs.size();

If you use TreeSet and make Pair implement Comparable, you'll have a sorted list of pairs

Set<Pair> pairs = new TreeSet<Pair>();
..
System.out.println(pairs);

Further, you can use a combination of List and Set and apply some logic to figure out exact number of duplicates etc, can also explore removeAll and retainAll for implementing logic.

Also, Map doesn't seem to be a fit in your use case since a class can wrap required mapping and list or set will help to apply desired logic over multiple pairs.

To get counts of total number of original pairs:

Set<Pair> pairs = new HashSet<Pair>();
int count =0;
while(..) { //iterating over list of pairs
    pairs.add(new Pair(prv, next));
    count ++;
   }
int uniquePairs = pairs.size();
int totalPairs = count;

Upvotes: 1

srikanta
srikanta

Reputation: 2999

You can create a custom class to store pairs of strings and then use a HashMap to keep track of the count

public class StringPair {
   String leftString;
   String rightString;

   //NOTE: override hashcode and equals methods
}

And then you can use HashMap for keeping tracking of the count:

Map<StringPair, Integer> pairCountMap = new HashMap<StringPair, Integer>();

if(pairCountMap.containsKey(aPairObject)) {
   pairCountMap.put(aPairObject, pairCountMap.get(aPairObject)+1);
} else {
   pairCountMap.put(aPairObject, 0);
}

Upvotes: 10

Related Questions