Рекурсивная функция для сопоставления строки с шаблоном подстановки - PullRequest
Новая
       16

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

9 голосов
/ 07 июня 2010

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

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

public static boolean samePattern(String s1, String s2)

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

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

Примеры:

1: TheExamIsEasy; 2: The*xamIs*y → верно
1: TheExamIsEasy; 2: Th*mIsEasy* → верно
1: TheExamIsEasy; 2: * → верно
1: TheExamIsEasy; 2: TheExamIsEasy → верно
1: TheExamIsEasy; 2: The*IsHard → FALSE

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

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

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

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

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);
}

Ответы [ 4 ]

6 голосов
/ 07 июня 2010

Вот некоторый псевдокод 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
5 голосов
/ 07 июня 2010

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

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

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

2 голосов
/ 07 июня 2010

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

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

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

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

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

2 голосов
/ 07 июня 2010

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

...