用于将字符串与通配符模式匹配的递归函数

Question

所以我一整天都试图解决这个任务,只是无法得到它.

以下函数接受2个字符串,第2个(不是第1个)可能包含*'s(星号).
An *是字符串的替换(空,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:？假

我尝试逐个比较字符,charAt直到遇到星号,然后通过比较连续的char(i+1)和s1at位置的char来检查星号是否为空i,如果为true,则继续递归,i+1作为s2&的计数器i反驳s1;
如果为false - 继续递归并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("ababababab","a*b")应返回true;*可以匹配除字符串的第一个和最后一个字母之外的所有字母,但是您的代码假定由于后面的字母是b,*匹配空字符串.

我建议将samePattern视为"消耗"其两个输入字符串,因为它会查找匹配项.在每个步骤中,samePattern应该只需要查看每个字符串的第一个字符,以确定是否可以匹配第一个字符,如果是,则进行递归调用以检查字符串的其余部分.当你在模式字符串中找到*时,诀窍将是知道该怎么做,因为它可能会或可能不会用于匹配s1中的第一个字符.您不应该查看字符串的其余部分来决定要做什么.

由于这是家庭作业,我会留下你在那里发生的事情的详细信息,但希望这会让你思考正确的道路.