CODEWITHSUNDEEP
javaalgorithm
user697911
user697911

Reputation: 10561

Fastest algorithm to find two strings that contains common characters

I want to find whether two Java strings contain 2 common characters, which have to be next to each other.

I am using two for loops to check for that, but it seems slow, because I have to compute it again and again.

boolean contain2CommonChars(String s1, String s2) {
     for(){
       for() {
       }
    }
}

Is there an efficient algorithms to do that?

Secondly, what I really want to do is to find a sentence subset A from　a large sentence set B given another sentence x. If any sentence from B has at least two common characters with sentence x, then put it into set A. 

Set<String> findSubset(Set<String> B, String x){
    Set<String> A = new HashSet<>();

    ...
    return A;      
}

By the way, the size of B <10,000. Can the findSubset() be done within a very few millseconds?

EDIT: The 2nd questions is closed related to the 1st question. Example:

B = {"this is a dog", "this is a bat", "that was an dog "}
x = "this is not a cat"

I want to return:

A = {"this is a dog", "this is a cat"} //  because of "this is" or "is a"

Upvotes: 0

Views: 151

Answers (3)

user1196549
user1196549

Reputation:

Only answering the first question.

If you have the possibility of preprocessing the strings, for every string generate all pairs of characters and sort them increasingly.

contain2CommonChars -> 2C ai ar Ch co Co ha in mm mo n2 nC nt om on on rs ta

Now common pairs between two strings are found by a single merge-like pass taking at most O(L).

Upvotes: 0

forpas
forpas

Reputation: 164194

By iteration through every adjacent pair of the shortest of the 2 strings: 

static boolean contain2CommonChars(String s1, String s2) {
    int l1 = s1.length();
    int l2 = s2.length();

    if ((l1 < 2) || (l2 < 2))
        return false;

    if (l2 < l1) {
        String temp = s1;
        s1 = s2;
        s2 = temp;
    }

    for (int i = 0; i < s1.length() - 1; i++){
        String pair = s1.substring(i, i + 2);
        if (s2.contains(pair))
            return true;
    }

    return false;
}

public static void main(String[] args) {
    String s1 = "abcghj";
    String s2 = "shhcgop";

    System.out.println(s1 + " and " + s2 + " " + contain2CommonChars(s1, s2));

    String s3 = "abcghjlo";
    String s4 = "shhcop";

    System.out.println(s3 + " and " + s4 + " " + contain2CommonChars(s3, s4));
}

prints

abcghj and shhcgop true
abcghjlo and shhcop false

Upvotes: 0

ninja.coder
ninja.coder

Reputation: 9658

Find whether two Java strings contain 2 common characters, which have to be next to each other.

There can be a lot of edge cases but here is a way to do it (Might not be the fastest but can work depending on your needs).

  • Iterate both the strings separately and create two HashSets for all 2-character pairs.

    For Example, foobar --> fo, oo, ob, ba, ar

  • Just take an intersection of the above created HashSets to see if there are any common pairs.

It's quite hard to understand the second question. Maybe try including an example to make it more clear.

Upvotes: 1

Related Questions