Рекурсивная функция, чтобы соответствовать строке с узором подстановочного знака

Question

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

Следующая функция принимает 2 строки, 2 -й (не 1 -е), возможно, содержащий *S (звездочки).
Атмосфера * является заменой струны (пустое, 1 char или больше), она может появиться (только в S2) один, два, два, больше или нет вообще, она не может быть рядом с другим * (ab**c) не нужно проверять это.

public static boolean samePattern(String s1, String s2)

Это возвращает истинность, если строки имеют одинаковую картину.
Это должно быть рекурсивный, не используйте какие -либо петли, статические и глобальные переменные. Может использовать локальные переменные и перегрузку метода.

Может использовать только эти методы: charAt(i), substring(i), substring(i, j), length().

Примеры:

1: TheExamIsEasy; 2: The*xamIs*y → True
1: TheExamIsEasy; 2: Th*mIsEasy* → True
1: TheExamIsEasy; 2: * → True
1: TheExamIsEasy; 2: TheExamIsEasy → True
1: TheExamIsEasy; 2: The*IsHard → Ложь

Я попытался сравнить чар за другим, используя charAt Пока звездочке не встречается, проверьте, является ли звездочка пустой при сравнении, является последовательным символом (i+1) с подростком s1 на позиции i, если это правда - продолжайте рекурсию с i+1 как счетчик для s2 & i как счетчик для s1;
Если неверно - продолжайте рекурсию с i+1 как счетчики для обоих.
Продолжайте это до тех пор, пока не найдено другое звездочке или конец строки.

Я не знаю, мой мозг теряет отслеживание вещей, не могу сконцентрироваться, ни один указатели / подсказки? Я в правильном направлении?

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

Мой код до сих пор (не выполняет работу, даже теоретически):

public static boolean samePattern(String s1, String s2) {
    if (s1.equals(s2) || s2 == "*") {
        return true;
    }
    return samePattern(s1, s2, 1);
}
public static boolean samePattern(String s1, String s2, int i)
{
    if (s1.equals(s2))
        return true;
    if (i == s2.length() - 1) // No *'s found -- not same pattern.
        return false;

    if (s1.substring(0, i).equals(s2.substring(0, i)))
        samePattern(s1, s2, i+1);
    else if (s2.charAt(i-1) == '*')
        samePattern(s1.substring(0, i-1), s2.substring(0, i), 1); // new smaller strings.
    else
        samePattern(s1.substring(1), s2, i);
}

Answer 1

Вот какой -то Python "псудокод", который может помочь

def samePattern(s1,s2):
    if s2 == "*" or s1 == s2: return True
    if s1 == "": return False
    if s1[0] == s2[0]: return samePattern(s1[1:], s2[1:])
    if s2[0] == "*": return samePattern(s1, s2[1:]) or samePattern(s1[1:], s2)
    return False

Вот приблизительное руководство для преобразования кода

s[0] = the first character
s[1:] = the string minus the first character

Answer 2

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

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

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

Answer 3

Вот пример решения, написанного в 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;
    }

Answer 4

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

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

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

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

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