Matching a subset in a row

Question

Say I have -

String x = "ab";
String y = "xypa";

If I want to see if there is any subset of x in y, what would be the fastest way? Looping takes a lot of time. In the above example, the subset of x is "a", which is located in y.

Answer 1

The answer really depends on many things.

If you just need to find a subset, and you do it only once, the loop is just good (and you can best do without using additional storage), and you can stop when you find one character that matches.

x y, x , , y x .

, : .

Answer 2

, , , , String#matches:

if (y.matches(".*[" + x + "]+.*")) ...

, regex [], (, ], -, \,...).

- , Pattern, Matcher, java.util.regex.

Answer 3

, , , .

, , , . , abc, abcdef.

:

• , , Java .
• , -, , .
• , , trie , .
• - : HashSet.

Answer 4

, , for, .

Boolean isSubset = false;
for(int i = 0; i < x.length(); i++) {
        if(y.contains(x.charAt(i))) {
                isSubset = true;
                break;
        }
}

for.

Answer 5

, .

Answer 6

x (, , ab, a, b), ,

  Pattern p = Pattern.compile("(ab|a|b)");
  Matcher m = p.matcher(y);
  if(m.find()) {
    System.err.println(m.group());
  }

Answer 7

[a-z]. , 26 . , . AND , , . O(n) n .

( UTF, .)

Answer 8

??

package so3935620;

import static org.junit.Assert.*;

import java.util.BitSet;

import org.junit.Test;

public class Main {

  public static boolean overlap(String s1, String s2) {
    BitSet bs = new BitSet();
    for (int i = 0; i < s1.length(); i++) {
      bs.set(s1.charAt(i));
    }
    for (int i = 0; i < s2.length(); i++) {
      if (bs.get(s2.charAt(i))) {
        return true;
      }
    }
    return false;
  }

  @Test
  public void test() {
    assertFalse(overlap("", ""));
    assertTrue(overlap("a", "a"));
    assertFalse(overlap("abcdefg", "ABCDEFG"));
  }
}

And if this version is too slow, you can calculate the bit-set depending on s1, save it in some variable, and later only through s2.