Найти соответствие для запроса в тексте

Question

Этот вопрос был задан недавно во время собеседования, и я не смог его решить, поэтому мне нужно несколько предложений, как я могу решить эту проблему

Заявление: я не могу использовать REGEX или любые встроенные библиотеки

***** Постановка задачи выглядит следующим образом: *********

** совпадений Входные данные: текст (строка), запрос (строка) Выходные данные: true, если вы можете найти соответствие длязапрос в тексте, в противном случае - false. Если специальных символов нет, в большинстве языков есть метод contains, который просто сделает это.Один специальный символ: «?»-- Если ты найдешь '?'в строке запроса он указывает, что предыдущий символ является необязательным (соответствует 0 или 1 раз).

Примеры:

• Нет вопросительных знаков:
• совпадений ("hello World", "hello") возвращает true
  • совпадений ("hello World", "world") возвращает false
  • совпадений ("hello World", "o W") возвращает true
  • совпадений ("hello World", "W o") возвращает false
  • совпадений ("hello World", "h W") возвращает false
  • с вопросительными знаками -- "Я?"означает «необязательный l»:
  • совпадений («heo World», «hel? o») возвращает истину
  • совпадений («helo World», «hel? o») возвращает истинные совпадения ("hello World", "hel? o") возвращает false
  • Убедитесь, что вы понимаете этот случай:
  • match ("hello World", "hell? lo") возвращает true
  • У вас может быть несколько знаков вопроса:
  • совпадений («Привет, мир», «ex? Llo ​​Worlds?») Возвращает значение true

***** Мой подход был таким, как показано ниже. *********

public class StringPatternMatch
{
    public static bool MatchPattern(string inputText, string pattern)
    {
        int count = 0; int patternIndex = 0;

        for (var i = 0; i < inputText.Length; i++)
        {
            if (patternIndex > pattern.Length)
                break;

            if (inputText[i] == pattern[patternIndex] ||
                (inputText[i] != pattern[patternIndex] && pattern[patternIndex + 1] == '?'))
                count++;

            patternIndex++;
        }

        return pattern.Length == count;
    }
}

пересекают обе строки с одной стороны на другую (скажем, от крайнего правого символа к крайнему левому).Если мы находим соответствующий символ, мы продвигаемся вперед в обеих строках с увеличивающимся счетчиком для шаблона - в конце счетчика совпадений с шаблоном-длиной

Также я предоставил свой код, но он не охватывает все случаи

Конечно, я не пошел в следующий раунд, но я все еще думаю об этой проблеме и не нашел точного решения - надеюсь увидеть некоторые интересные ответы!

Answer 1

Ваша идея может работать, но ваша реализация слишком упрощена:

// assumes the pattern is valid, e.g. no ??
public static boolean matches(String string, String pattern) {
    int p = 0; // position in pattern
    // because we only return boolean we can discard all optional characters at the beginning of the pattern
    while (p + 1 < pattern.length() && pattern.charAt(p + 1) == '?')
        p += 2;
    if (p >= pattern.length())
        return true;
    for (int s = 0; s < string.length(); s++) // s is position in string
        // find a valid start position for the first mandatory character in pattern and check if it matches
        if (string.charAt(s) == pattern.charAt(p) && matches(string, pattern, s + 1, p + 1))
            return true;
    return false;
}

private static boolean matches(String string, String pattern, int s, int p) {
    if (p >= pattern.length()) // end of pattern reached
        return true;
    if (s >= string.length() || string.charAt(s) != pattern.charAt(p)) // end of string or no match
        // if the next character of the pattern is optional check if the rest matches
        return p + 1 < pattern.length() && pattern.charAt(p + 1) == '?' && matches(string, pattern, s, p + 2);
    // here we know the characters are matching
    if (p + 1 < pattern.length() && pattern.charAt(p + 1) == '?') // if it is an optional character
        // check if matching the optional character or skipping it leads to success
        return matches(string, pattern, s + 1, p + 2) || matches(string, pattern, s, p + 2);
    // the character wasn't optional (but matched as we know from above)
    return matches(string, pattern, s + 1, p + 1);
}