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

Question

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

是否有用于此目的的标准功能？如果没有,那么这个问题的良好实施是什么？(当然我可以为我的s2中的每个char 运行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).