Java, string difference algorithm

Question

I would like to get a feedback about the code below. Is there any way to improve it's performance? Maybe you know input values that might print bad output? The idea of the code is to count unique characters from s2 that are not listed in s1. Ideone.com URL.

The code:

class Combine {
    public static void main(String[] args) throws IOException {
        BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
        String s1 = bi.readLine();
        String s2 = bi.readLine();

        String usedCharacters = "";

        for(int i = 0; i < s2.length(); i++) {
            String c = Character.toString(s2.charAt(i));
            if(!usedCharacters.contains(c) && !s1.contains(c)) 
                usedCharacters += c;
        }

        System.out.println(usedCharacters.length());
    }
}

FYI, questions about optimizing existing working code are better suited for codereview.se — merours
– merours, Commented Dec 8, 2014 at 15:23
This question appears to be off-topic because it is about optimizing an existing code that is not broken. Consider posting to codereview.stackexchange.com instead. — Sergey Kalinichenko
– Sergey Kalinichenko, Commented Dec 8, 2014 at 15:24

davidahines · Accepted Answer · 2014-12-08 16:00:40Z

1

I think this is fairly well optimized but you should probably check for null, as it will fail if you pass it null values.

answered Dec 8, 2014 at 16:00

davidahines

4,11417 gold badges56 silver badges88 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Hristo Yordanov · Accepted Answer · 2014-12-08 15:24:25Z

0

I think this performance is good enough and any improvements would not make a sensitive difference.

answered Dec 8, 2014 at 15:24

Hristo Yordanov

394 bronze badges

1 Comment

user3058763 Over a year ago

What about an input? Do you know any values which this code might fall with?

iozee · Accepted Answer · 2014-12-08 15:30:28Z

0

I think you should try to iterate over the larger or the smaller String (measure the time overhead) - that's where you can save some CPU time.

answered Dec 8, 2014 at 15:30

iozee

1,3581 gold badge13 silver badges25 bronze badges

Comments

darrenmc · Accepted Answer · 2014-12-08 16:42:33Z

0

If your input is relatively small (eg typed by a user on the console) then I see no performance problem with your solution (apart from the null checks as suggested by another answer).

If the input is large, eg redirected files on the command line of megabytes or more then I think your solution will yield O(n^2) run time performance as it iterates though s2 and the contains method call will also iterate across the whole string.

An alternative algorithm would be to sort the two input strings and then iterate across them to count the differences. That would result in O(n log n) performance.

answered Dec 8, 2014 at 16:42

darrenmc

1,7811 gold badge20 silver badges29 bronze badges

Comments

roinir · Accepted Answer · 2014-12-08 16:52:35Z

0

Didn't try it but here's an idea:

class Combine {
public static void main(String[] args) throws IOException {
    BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
    String s1 = bi.readLine();
    String s2 = bi.readLine();

    int count = 0;
    for(char c : new HashSet<Char>(s2.toCharArray())) {
     if(s1.contains(c)) count++
    }


    System.out.println(count);
}

}

answered Dec 8, 2014 at 16:52

roinir

3002 silver badges9 bronze badges

Collectives™ on Stack Overflow

Java, string difference algorithm

5 Answers 5

Comments

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related