Рекурсивная функция для соответствия строке против подстановочного шаблона

Вот пример решения, написанного на C #. Извините за отсутствие комментариев, но у меня не было на них времени: / Если они вам еще понадобятся завтра, я могу написать несколько, но я надеюсь, что вы ухватитесь за идею.

 public static bool CompareString(string s1, string s2, bool wildCard)
 {
        // Both strings are empty
        if ((s1.Length == 0) && (s2.Length == 0)) return true;

        // Second string is empty and there is wildCard character
        if (s2.Length == 0 && wildCard) return true;

        //First string is empty. Answer will be true only if all characters in second string are *.
        if (s1.Length == 0 && s2.Length > 0 && s2[0] == '*')
        {
            string newS2 = s2.Remove(0, 1);
            return CompareString(s1, newS2, true);
        }

        // One of the strings is empty, and second one is not.
        if (s1.Length * s2.Length == 0) return false;

        if (wildCard)
        {
            string newS1 = s1.Remove(0, 1);
            if (CompareString(newS1,s2,true) || CompareString(newS1,s2,false))
            {
                return true;
            }
        }
        else
        {
            if (s2[0] == '*')
            {
                string newS2 = s2.Remove(0,1);
                if (CompareString(s1,newS2,true) || CompareString(s1,newS2,false))
                {
                    return true;
                }
            }
            else
            {
                if (s1[0] == s2[0])
                {
                    string newS1 = s1.Remove(0,1);
                    string newS2 = s2.Remove(0,1);
                    return CompareString(newS1,newS2,false);
                }
                else
                {
                    return false;
                }
            }
        }
        return false;
    }

Когда вы имеете дело с подобными алгоритмами, часто бывает полезно разбить проблему на небольшие кусочки в уме.

Поскольку вы анализируете строку, рассмотрите решение по каждому символу. Более того, поскольку вы не можете контролировать фактический размер этих строк, ограничьте себя рассмотрением только первого символа строки в любой момент времени.(хорошо - с одним исключением)

После того, как вы определили, что персонажи, с которыми вы имеете дело, требуют дальнейшего исследования остальной части строки, выбросьте их ; их хранение только добавляет сложности, так зачем беспокоиться? (И наоборот, если символы полностью не совпадают, все готово - верно?)

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

У меня есть алгоритм, который я придумал (11 строк кода плюс фигурные скобки), который я могу опубликовать, если вам нужно полное решение, но я не был уверен в вашем сообщении, хотите ли вы, чтобы вам дали алгоритм, или просто указатели.

Проблема с вашим текущим подходом заключается в том, что он не учитывает все возможные подстроки, которые * может соответствовать. Например, samePattern («ababababab», «a * b») должен возвращать true; * может соответствовать всем буквам строки, кроме первой и последней, но ваш код предполагает, что, поскольку следующая буква - b, * соответствует пустой строке.

Я предлагаю думать о samePattern как о «потреблении» двух своих входных строк при поиске совпадения. На каждом шаге samePattern должен смотреть только на первый символ каждой строки, чтобы решить, возможно ли совпадение с первым символом , и если да, то сделать рекурсивный вызов для проверки остальной части строки. Хитрость заключается в том, чтобы знать, что делать, когда вы дойдете до * в строке шаблона, поскольку он может использоваться или не использоваться для сопоставления первого символа в s1. Вам не нужно смотреть на оставшуюся часть строки, чтобы решить, что делать.

Поскольку это домашнее задание, я оставлю выяснение деталей того, что там происходит с вами, но, надеюсь, это заставит вас задуматься о правильном пути.