Two string comparison

Question

I wrote a function that finds the difference between two strings. This only works given that the difference is continuous.

Beyond doubt this already exists, I am recreating this for educational purposes. I would like feedback about my performance and efficiency.

Examples of this method:

String difference = Difference("Hello", "Hello world!");
//difference would be " world!"

String difference = Difference("Removing text", "Removi");
//difference would be "ng text"

String difference = Difference("same size", "SAME size");
//difference would be "SAME"

public static String Difference(String string1, String string2)
{
    int size = string2.length() - string1.length();
    if(size < 0)
    {
        size *= -1;
        String swap = string1;
        string1 = string2;
        string2 = swap;
    }
    String difference = "";
    int start = DifferenceStartIndex(string1, string2);
    if(size > 0)
        for(int i = start; i < start + size; i++)
            difference += string2.charAt(i);
    else
    {
        if(start != -1)
        {
            int end = DifferenceEndIndex(string1, string2, start);
            for(int i = start; i < end; i++)
                difference += string2.charAt(i);
        }
        else
            return "";
    }
    return difference;
}

public static int DifferenceStartIndex(String string1, String string2)
{
    int maxSize = (string1.length() > string2.length()) ? string1.length() : string2.length();
    for(int i = 0; i < maxSize; i++)
        if(((i < string1.length()) ? string1.charAt(i) : '\0') != ((i < string2.length()) ? string2.charAt(i) : '\0'))
            return i;
    return -1;
}

public static int DifferenceEndIndex(String string1, String string2, int start)
{
    int maxSize = (string1.length() > string2.length()) ? string1.length() : string2.length();
    int end = maxSize;
    for(int i = start; i < maxSize; ++i)
        if(string1.charAt(i) != string2.charAt(i))
            end = i + 1;
    return end;
}

Welcome to Code Review! I moved your description to the top because that way it shows up with a description on the front page. If a question just starts with a code block then instead of showing some of your description there's just ... under your question title. Try to explain first than paste in the code in future. — SuperBiasedMan
– SuperBiasedMan, Commented Oct 21, 2015 at 14:42
A pair of testcases would make reviewing easier, it would be nice to add them. — Caridorc
– Caridorc, Commented Oct 21, 2015 at 14:49
@Caridorc I added examples? The function is working, I just want to improve on efficiency. — Omar Chehab
– Omar Chehab, Commented Oct 21, 2015 at 14:57
@OmarChehab, what happens if string2 is somewhere in the middle of string1, is that situation expected? For example, "Removing stuff" and "moving". — Gentian Kasa
– Gentian Kasa, Commented Oct 21, 2015 at 15:06
@Caridorc Sorry, I typo'd the question mark. I added examples, thank you for your advice! — Omar Chehab
– Omar Chehab, Commented Oct 21, 2015 at 15:09

Community · Accepted Answer · 2020-06-10 13:24:26Z

Conventions

In java, methods begin with a lowercase letter.

Design

Methods should be private unless they are required by clients. In this case, only the difference() method should be public.

Implementation

There are a few things to look at here. First, your code is made much more complex by swapping around the two inputs based on size. It would be neater if you did the size comparison once, then called a helper method with parameters shorterString and longerString.

Your two size methods are clunky because they don't return early when they find a (mis)match, and because they run off of the longer string rather than the shorter string.

There may be a slight performance gain to be made if the two strings are frequently equal. In that case only, it may be faster to check if the two strings are equals() and return -1 from differenceStartIndex() right away. In your particular case, I highly doubt this check would be anything more than clutter.

Applying these changes might make the code look something like:

public final class Difference {

    public static String difference(final String string1, final String string2) {
        if (string1.length() <= string2.length()) {
            return differenceHelper(string1, string2);
        }
        return differenceHelper(string2, string1);
    }

    private static String differenceHelper(final String shorterString, final String longerString) {
        final int start = differenceStartIndex(shorterString, longerString);
        if (start < 0) {
            return "";
        }
        final int end = differenceEndIndex(shorterString, longerString, start);
        return longerString.substring(start, end);
    }

    private static int differenceStartIndex(final String shorterString, final String longerString) {
        for (int i = 0; i < shorterString.length(); i++) {
            if (shorterString.charAt(i) != longerString.charAt(i)) {
                return i;
            }
        }

        if (shorterString.length() == longerString.length()) {
            return -1;
        }

        return shorterString.length();
    }

    private static int differenceEndIndex(final String shorterString, final String longerString, final int startIndex) {
        for (int i = startIndex; i < shorterString.length(); i++) {
            if (shorterString.charAt(i) == longerString.charAt(i)) {
                return i + 1;
            }
        }
        return longerString.length();
    }

    public static void main(final String[] argv) {
        System.out.println(Difference.difference("Hello", "Hello world!"));
        System.out.println(Difference.difference("Removing text", "Removi"));
        System.out.println(Difference.difference("same size", "SAME size"));

    }
}

@OmarChehab Note that this does not correctly handle the case I asked about above. It always uses the longer string's difference. It may be invalid or require tweaking to match that case. I'm not sure why difference("same", "samE") is "E", but difference("same2", "same") is "2", and I don't see a good way to make a general rule to fit that case. Hopefully this will give you a decent starting point. — Eric Stein
– Eric Stein, Commented Oct 21, 2015 at 16:11
I intend the return to be "E" in that case because it is the value that was modified. — Omar Chehab
– Omar Chehab, Commented Oct 21, 2015 at 16:28

Gentian Kasa · Accepted Answer · 2015-10-21 15:17:50Z

0

I'd suggest the following:

    String swap = string1;
    string1 = string2;
    string2 = swap;

should be moved to another method (in order to follow the Separation of Concerns principle).

In your methods, you access string.length() too many times (even in cycles). Given that the length doesn't change I'd suggest to memorize it in an int variable.

For readability's sake, you could transform int maxSize = (string1.length() > string2.length()) ? string1.length() : string2.length(); into int maxSize = Math.max(string1.length(), string2.length());

That being said, if performance is key, I'd overload the methods with some other methods that work directly with char[] instead of String and contain all the logic and call those from the methods working with String.

edited Oct 21, 2015 at 15:17

answered Oct 21, 2015 at 15:03

Gentian Kasa

2,09616 silver badges24 bronze badges

\$\begingroup\$ Thank you for your feedback, I have added the changes. I do not understand why swap should have a method of itself. The single responsibility principle applies to classes, but not methods? Correct me if I am wrong. \$\endgroup\$

Omar Chehab
– Omar Chehab

2015-10-21 15:13:20 +00:00
Commented Oct 21, 2015 at 15:13
\$\begingroup\$ You shouldn't change the original code you posted as it becomes unclear which version is to be reviewed. \$\endgroup\$

Gentian Kasa
– Gentian Kasa

2015-10-21 15:19:55 +00:00
Commented Oct 21, 2015 at 15:19
\$\begingroup\$ @OmarChehab it was the Separation of Concerns principle. I edited the answer. \$\endgroup\$

Gentian Kasa
– Gentian Kasa

2015-10-21 15:21:10 +00:00
Commented Oct 21, 2015 at 15:21
\$\begingroup\$ Thanks, however, the latest should be the one to be reviewed. \$\endgroup\$

Omar Chehab
– Omar Chehab

2015-10-21 15:37:17 +00:00
Commented Oct 21, 2015 at 15:37
\$\begingroup\$ It kinda goes against the rules of the site :-) \$\endgroup\$

Gentian Kasa
– Gentian Kasa

2015-10-21 15:39:03 +00:00
Commented Oct 21, 2015 at 15:39

| Show 2 more comments

Stack Exchange Network

Two string comparison

2 Answers 2

Conventions

Design

Implementation

You must log in to answer this question.

Hot Network Questions

Two string comparison

2 Answers 2

Conventions

Design

Implementation

You must log in to answer this question.

Related

Hot Network Questions