Найти первое вхождение любого символа строки в другой строке

Question

У меня проблема: мне нужно найти первое вхождение любой символ из строки s2 (или массив символов) в строке s1 .

Существует ли стандартная функция для этой цели?Если нет, какова хорошая реализация для этой проблемы?(Конечно, я могу запустить indexOf для каждого символа из моего s2, но это не похоже на хороший алгоритм, потому что если только последний символ встречается в 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)в алгоритме, который вы описываете.

Answer 2

Использование регулярного выражения:

   public static void main(final String[] args) {
      final String s1 = "Hello World";
      final String s2 = "log";

      final Pattern pattern = Pattern.compile("[" + Pattern.quote(s2) + "]");
      final Matcher matcher = pattern.matcher(s1);
      if (matcher.find()) {
         System.out.println(matcher.group());
      }
   }

Answer 3

Что подразумевается под символом в этом контексте?Если это просто 16-битная Java char, это просто.Создайте таблицу поиска (массив) для всех возможных значений, указав, появляются ли они в s2.Затем переходите через s1, пока либо не найдете символ из s2, либо пока не достигните конца s1.Если символ является кодовой точкой Юникода, это более сложно, но вышеизложенный дает метод, чтобы выяснить, где вам нужно присмотреться.

Answer 4

То, что вы ищете, это indexOfAny от Apache StringUtils.

Похоже, что реализация:

 public static int indexOfAny(String str, char[] searchChars) {
   if (isEmpty(str) || ArrayUtils.isEmpty(searchChars)) {
     return -1;
   }
   for (int i = 0; i < str.length(); i++) {
     char ch = str.charAt(i);
       for (int j = 0; j < searchChars.length; j++) {
         if (searchChars[j] == ch) {
           return i;
         }
       }
     }
    return -1;
  }