子集

Question

比方说，我有─

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

如果我想看看X的任何子集y中存在，这将是最快的方法是什么？循环很耗时。在上面的例子中，x的一个子集是在y中找到的“a”。

Answer 1

好了，我不知道这是不是循环更好，但你可以使用String#matches：

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

你需要转义是在一个正则表达式[]构造特殊字符，但（像]， -,\，...）。

以上只是一个例子，如果您不止一次这样做，您需要使用Pattern,Matcher以及java.util.regex package中的其他内容。

Answer 2

循环过程非常耗时，但除了重复执行目标字符串之外，没有办法做到您想要的操作。

你可以做的是通过首先检查最小的字符串进行优化，然后继续工作。例如，如果目标字符串不包含abc，则它不可能包含abcdef。

了我的头顶部其他优化：

• 不要继续检查匹配不匹配的字符被击中后，虽然在Java中，你可以让这个电脑的担心。
• 如果目标字符串中没有足够的字符可用于匹配，请不要检查是否匹配。
• 如果您需要速度并且有足够的空间，您可能可以将目标字符串分解为像trie这样的奇特数据结构，以获得更好的结果，但我并没有考虑精确的算法。
• 另一个存储不是问题的解决方案：将目标分解为每个可能的子字符串并将结果存储在HashSet中。

Answer 3

你必须使用循环或使用正则表达式，它与for循环一样昂贵，因为你需要将你的一个字符串转换为字符。

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

使用for循环。

Answer 4

看起来这可能是longest common substring problem的情况。

Answer 5

答案真的取决于很多事情。

如果你只是想找个任何子集，你这样做只有一次，循环就好了（你可以无需使用额外的存储做了最好的），当你发现一个字符，你可以停止火柴。

如果你有一个固定的x，想用它来匹配多个字符串y，你可以做一些预处理的字符存储在x在一个表中，并使用此表来检查的y每个字符中出现是否或不是。

如果你想找到最大的子集，那么你正在看一个不同的问题：longest common subsequence problem。

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")); 
    } 
} 

如果该版本是太慢了，你可以计算取决于s1位集，保存在某个变量，后来只在s2循环。