递归功能使字符串与通配符模式匹配

Question

因此，我一直在尝试整天解决这项任务，只是无法理解。

以下功能接受2个字符串，第二个（不是第一）可能包含 *（星号）。
一个 * 是替代字符串（空，1个字符或更多）的替代品，它可以出现（仅在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 →正确
1: TheExamIsEasy; 2: Th*mIsEasy* →正确
1: TheExamIsEasy; 2: * →正确
1: TheExamIsEasy; 2: TheExamIsEasy →正确
1: TheExamIsEasy; 2: The*IsHard →错误

我尝试使用 charAt 在遇到星号之前，请通过比较是连续的char检查星号是一个空的（是否为空）（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的“ psudocode”，可能会有所帮助

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（“ Abababab”，“ 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行代码，以及括号） - 但是如果您想获得算法或仅仅是指示器，我不确定您的消息不确定。