java - 在其他字符串中查找字符串的任何符号的第一次出现

Question

我有一个问题:我需要从字符串s2(或字符数组)中找到任何符号在字符串s1中的第一次出现.

是否有用于此目的的标准函数？如果没有，这个问题的好的实现是什么？ (当然，我可以为我的 s2 中的每个字符运行 indexOf，但这似乎不是一个好的算法，因为如果只有最后一个符号出现在 s1 中，我们必须运行 s1 |s2|-1 次才能得到答案)。

非常感谢!

Answer 1

将 s2 中的所有字符放入恒定时间查找数据结构(例如 HashSet )。遍历 s1 中的每个字符并查看您的数据结构是否包含该字符。

大致(未经测试):

public int indexOfFirstContainedCharacter(String s1, String s2) {
  Set<Character> set = new HashSet<Character>();
  for (int i=0; i<s2.length; i++) {
    set.add(s2.charAt(i)); // Build a constant-time lookup table.
  }
  for (int i=0; i<s1.length; i++) {
    if (set.contains(s1.charAt(i)) {
      return i; // Found a character in s1 also in s2.
    }
  }
  return -1; // No matches.
}

此算法是 O(n)，而不是您描述的算法中的 O(n^2)。