Sorting Strings and extracting common elements of two String arrays in Java

Question

I was asked to write down a Java function sharedStr that by given 2 sorted arrays of Strings, returns the number of Strings that appear in both of the arrays.

The solution for this code must be linear, which means that I must go through each array only once. Otherwise, I could just compare each String in the first array to all the Strings in the other array.

For example the following call to sharedStr

sharedStr({"Call","me","Ishmael"},{"Call","me","Jonha"});

must return 2. I would like your help to understand what does it mean sorted arrays that contain Strings? There isn't any special description of the way the arrays have been sorted. What is the basic ordinary sorting of Strings?

How does one compare between two Strings anyway? If I try to do so, I get a compiler error. (I'm using Eclipse. I noticed that chars can be compared automatically).

Answer 1

What does it mean sorted arrays that contains strings? There isn't any special description of the way it has been sorted. what is the basic ordinary sorting of strings?

It means the elements in the array are ordered in a natural sequence. For strings this is alphebetical order with lowercase words place before upper case.

How does one compare between two strings any way?

By invoking the compareTo method. If it returns 0 they strings are equal, if return < 0 the first string is lower than the second, if return > 0 the firs string is higher than the second.

As for how to count repetitions linearly see this: comparing strings in java

Answer 2

1. Strings are usually ordered in lexicographic fashion (alphabetical). However, as long as the ordering is consistent, the exact ordering method is not important for this problem (they could be reverse sorted for instance).
2. Java compares objects (not object references) using .equals() (for boolean) or .compareTo() (for relational comparison) For instance:

.

String a = "Hello";
a.equals("Hello"); // true
String b = "Not hi";
b.equals(a); // false

Be careful accidentally using == - for constant strings, due to VM designs, it may actually say two Strings are equal, as they are in fact the same object.

Answer 3

int x =  0;
int i= 0;
int j = 0;
while(i != list1.length && j != list2.length){
  int v = list1[i].compareTo(list2[j]);
  if (v == 0){
    x++;i++;j++;
  }else if (v < 0){
    i++;
  } else {
    j++;
  }
}
return x;

This makes the straightforward assumption that the strings are sorted using String.compareTo which would make sense.

Answer 4

If nothing was specified on what the ordering means, then it's probably indicative that it is the natural ordering of Strings which is lexicographic - from the JavaDoc for the appropriate function to compare two Strings - compareTo(), the definition of lexicographic ordering is copied and pasted below.

Note that using compareTo() is different from simply checking the equality of two strings which is done using the equals() method (and not the == operator which doesn't doesn't check for 'meaningful' equality, only referential equality); compareTo on the other hand will tell you what the relative ordering between two strings is i.e. are they equal (return value of 0) or does one come before the other?):

This is the definition of lexicographic ordering. If two strings are different, then either they have different characters at some index that is a valid index for both strings, or their lengths are different, or both. If they have different characters at one or more index positions, let k be the smallest such index; then the string whose character at position k has the smaller value, as determined by using the < operator, lexicographically precedes the other string. In this case, compareTo returns the difference of the two character values at position k in the two string -- that is, the value:

 this.charAt(k)-anotherString.charAt(k)

If there is no index position at which they differ, then the shorter string lexicographically precedes the longer string. In this case, compareTo returns the difference of the lengths of the strings -- that is, the value:

 this.length()-anotherString.length()

This effectively means they're ordered alphabetically with shorter strings in lower case first, just like in a dictionary.

Answer 5

First, the second part of your question:

Comparing strings in Java isn't as simple as:

if(sStringOne == sStringTwo)
    //Equal

you should instead use methods of the string class

if(sStringOne.equals(sStringTwo)
    // Equal

Second, the first part of your question:

Yes, it would be easy to loop through the first array and count each indexs occurence in the second array. Since you've specified each array must be iterated only once however, perhaps the following algorithm may suit:

1. Create an integer variable initialised to zero to count the matching occurences.
2. Loop through array one 2.1 For each index, check to see if it's string is present in the other array, do this with the contains function contains function example 2.2 If string is found in other array, increment counter.
3. read the counter, this is the number of matching strings

Answer 6

Go with the assumption that the two lists are sorted before entering your sharedStr algorithm. You'd want to keep two references: each to an element in each of the two lists.

Then you'd start comparing element after element and progress either or both of the references accordingly. Here's a pseudo-code:

def sharedStr(lista, listb):
    indexa = indexb = 0
    shared = 0

    while 1:
        try:
            a = lista[indexa]
            b = listb[indexb]
        except IndexError:     # we fell off one of the lists
            break

        if a == b:
            shared += 1
            indexa += 1
            indexb += 1
        elif a < b:
            indexa += 1
        else:    # b < a
            indexb += 1

    return shared

Yes, this is also a valid Python code. ;-)

Answer 7

Because the arrays are sorted, you can step through them knowing you're walking them in order.

import java.util.List;
import java.util.LinkedList;
class StringTest {
    static List<String> sharedStrings(String[] a, String[] b) {
        List<String> result = new LinkedList<String>();
        int apos = 0;
        int bpos = 0;
        while(!(apos == a.length || bpos == b.length)) {
            int comp = a[apos].compareTo(b[bpos]);
            if(comp == 0) result.add(a[apos++]);
            else if(comp > 0) bpos++;
            else apos++;
        }
        return result;
    }
    public static void main(String[] args) {
        String[] a = new String[]{"this","is","a","test"};
        String[] b = new String[]{"test","for","a","party"};

        java.util.Arrays.sort(a);
        java.util.Arrays.sort(b);

        List<String> result = sharedStrings(a,b);
        for(String s : result) System.out.println(s);

    }
}

Answer 8

The fact that the arrays are sorted is a red herring, it is irrelevant to the solution. Use a Map<String, Integer> Steps:

1. For each string in the first array do the following:
   1. do a map.get(currentString)
   2. if that is null, do a map.put(currentString, new Integer(0))
2. For each string in the second array do the following:
   1. do a map.get(currentString)
   2. if that is null, ignore it, it is not a duplicate.
   3. If that is not null, do a map.put(currentString, new Integer(currentInteger.intValue() + 1);
3. do a map.getKeySet().iterator() and iterate through the keys.
4. for each key, get the value. The value is the count of strings that are in both arrays.