Блог

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

Объявление: я не могу использовать регулярные ВЫРАЖЕНИЯ или какие-либо встроенные библиотеки

***** Формулировка проблемы выглядит следующим образом*********

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

Примеры:

• Нет вопросительных знаков:
• совпадения («привет, мир», «привет») возвращает true
  • совпадения («hello World», «world») возвращает false
  • совпадения («hello World», «o W») возвращает true
  • совпадения («hello World», «W o») возвращает false
  • совпадения («hello World», «h W») возвращает false
  • С вопросительными знаками — «l?» означает «необязательный l»:
  • совпадения («heo World», «hel?o») возвращает true
  • совпадения («helo World», «helo») возвращает true совпадения («hello World», «helo») возвращает false
  • Убедитесь, что вы понимаете этот случай:
  • совпадения («hello World», «hell?lo») возвращает true
  • У вас может быть более одного вопросительного знака:
  • совпадения («привет, мир», «из каких миров?») возвращает 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] amp;amp; pattern[patternIndex   1] == '?'))
                count  ;

            patternIndex  ;
        }

        return pattern.Length == count;
    }
}
  

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

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

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

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

 // 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() amp;amp; 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) amp;amp; 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() amp;amp; pattern.charAt(p   1) == '?' amp;amp; matches(string, pattern, s, p   2);
    // here we know the characters are matching
    if (p   1 < pattern.length() amp;amp; 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);
}