java - 使用 Java HashSet 的两个字符串的交集

Question

我正在尝试通过做一些斯坦福类(class)的作业来学习 Java，但在回答这个问题时遇到了麻烦。

boolean stringIntersect(String a, String b, int len): Given 2 strings, consider all the substrings within them of length len. Returns true if there are any such substrings which appear in both strings. Compute this in O(n) time using a HashSet.

我无法弄清楚如何使用 Hashset 来做到这一点，因为您无法存储重复字符。所以 stringIntersect(hoopla, loopla, 5) 应该返回 true。

谢谢!

编辑:非常感谢您的及时回复。查看解释和代码很有帮助。我想我不明白为什么将子字符串存储在哈希集中会使算法更有效。我最初有一个解决方案，如:

public static boolean stringIntersect(String a, String b, int len) {
    assert (len>=1);
    if (len>a.length() || len>b.length()) return false;
    String s1=new String(),s2=new String();
    if (a.length()<b.length()){
        s1=a;
        s2=b;
    }
    else {
        s1=b;
        s2=a;
    }
    int index = 0;
    while (index<=s1.length()-len){
        if (s2.contains(s1.substring(index,index+len)))return true;
        index++;
    }
    return false;
}

Answer 1

我不确定我理解你所说的“你不能存储重复字符”是什么意思哈希集是一个 Set ，所以它可以做两件事:你可以向它添加值，你可以向它添加值，你可以检查如果一个值已经在其中。在这种情况下，问题希望您通过在 HashSet 中存储字符串而不是字符来回答问题。要在 Java 中执行此操作:

Set<String> stringSet = new HashSet<String>();

试着把这个问题分成两部分:
1.生成一个字符串的所有长度为 len的子串
2. 用它来解决问题。

第二部分的提示是:
步骤 1:对于第一个字符串，将子字符串输入到哈希集中
步骤 2:对于第二个字符串，检查哈希集中的值

注意(高级):这个问题没有详细说明。在哈希表中输入和检查字符串是字符串的长度。对于长度为 n 的字符串 a，您有 O(n-k) 个长度为 k 的子字符串。因此，对于 string a 是一个长度为 n 的字符串而字符串 b 是一个长度为 m 的字符串，你有 O((n-k)*k+(m-k)*k) 这并不是 n 的很大哦，因为 k = n/2 的运行时间是 O((n/2)*( n/2)) = O(n^2)

编辑:那么，如果您真的想在 O(n) (或 O(n+m+k) )中执行此操作怎么办？我的信念是，最初的作业要求类似于我上面描述的算法。但我们可以做得更好。更重要的是，我们可以做得更好，并且仍然使 HashSet 成为我们算法的关键工具。这个想法是使用“滚动哈希”来执行我们的搜索。维基百科描述了一对: http://en.wikipedia.org/wiki/Rolling_hash ，但我们将实现我们自己的。

一个简单的解决方案是将字符散列的值异或在一起。这可以让我们向散列 O(1) 添加一个新字符并删除一个 O(1) 使计算下一个散列变得微不足道。但是这个简单的算法由于两个原因不起作用

字符散列可能无法提供足够的熵。好吧，我们不知道我们是否会遇到这个问题，但无论如何让我们解决它，只是为了好玩。

我们会将排列散列到相同的值......“abc”不应与“cba”具有相同的散列

为了解决第一个问题，我们可以使用 AI 的一个想法，即 let steel from Zobrist hashing 。这个想法是为每个可能的字符分配一个更大长度的随机值。如果我们使用 ASCI，我们可以轻松地创建一个包含所有 ASCI 字符的数组，但是在使用 unicode 字符时会遇到问题。另一种方法是懒惰地分配值。

object LazyCharHash{
  private val map = HashMap.empty[Char,Int]
  private val r = new Random
  def lHash(c: Char): Int = {
    val d = map.get(c)
    d match {
      case None => {
        map.put(c,r.nextInt)
        lHash(c)
      }
      case Some(v) => v
    }
  }
}

这是 Scala 代码。 Scala 往往不如 Java 冗长，但仍允许我使用 Java 集合，因此我将始终使用命令式 Scala。翻译起来不会那么难。

第二个问题也可以解决。首先，我们不使用纯异或，而是将异或与移位相结合，因此哈希函数现在是:

def fullHash(s: String) = {
  var h = 0
  for(i <- 0 until s.length){
    h = h >>> 1
    h = h ^ LazyCharHash.lHash(s.charAt(i))
  }
  h
}

当然，使用 fullHash 不会带来性能优势。这只是一个规范

我们需要一种使用我们的哈希函数在 HashSet 中存储值的方法(我 promise 我们会使用它)。我们可以创建一个包装类:

class HString(hash: Int, string: String){
  def getHash = hash
  def getString = string
  override def equals(otherHString: Any): Boolean = {
    otherHString match {
      case other: HString => (hash == other.getHash) && (string == other.getString)
      case _ => false
    }
  }
  override def hashCode = hash
}

好的，为了使散列函数滚动，我们只需要对与我们不再使用的字符关联的值进行异或。只需将该值移动适当的量即可。

def stringIntersect(a: String, b: String, len: Int): Boolean = {
  val stringSet = new HashSet[HString]()
  var h = 0
  for(i <- 0 until len){
    h = h >>> 1
    h = h ^ LazyCharHash.lHash(a.charAt(i))
  }
  stringSet.add(new HString(h,a.substring(0,len)))
  for(i <- len until a.length){
    h = h >>> 1
    h = h ^ (LazyCharHash.lHash(a.charAt(i - len)) >>> (len))
    h = h ^ LazyCharHash.lHash(a.charAt(i))
    stringSet.add(new HString(h,a.substring(i - len + 1,i + 1)))
  }
  ...

您可以自行弄清楚如何完成此代码。

这是 O(n) 吗？嗯，重要的是什么意思。大哦，大 Omega，大 Theta，都是界限的度量。它们可以作为算法最坏情况、最好情况或其他情况的指标。在这种情况下，这些修改为 提供了预期的 O(n) 性能，但这只有在我们避免哈希冲突的情况下才有效。仍然需要 O(n) 来判断两个字符串是否相等。这种随机方法效果很好，您可以扩大随机位数组的大小以使其更好地工作，但它不能保证性能。