用于将字符串与通配符模式匹配的递归函数
所以我一整天都试图解决这个任务，只是无法得到它。
以下函数接受2个字符串，第2个（不是第1个）可能包含* （星号）。
*是字符串的替换（空，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 →true
1： TheExamIsEasy ; 2： Th*mIsEasy* →true
1： TheExamIsEasy ; 2： * →true
1： TheExamIsEasy ; 2： TheExamIsEasy →true
1： TheExamIsEasy ; 2： The*IsHard →FALSE
我尝试使用charAt逐个比较字符，直到遇到星号，然后通过比较连续的char（ i+1 ）和位置i的s1的char来检查星号是否为空 – 如果为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); }
这里有一些可能有用的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
您当前方法的问题在于它没有考虑a *可以匹配的所有可能的子串。 例如，samePattern（“ababababab”，“a * b”）应返回true; *可以匹配除字符串的第一个和最后一个字母之外的所有字母，但是您的代码假定由于后面的字母是b，*匹配空字符串。
我建议将samePattern视为“消耗”其两个输入字符串，因为它会查找匹配项。 在每个步骤中，samePattern应该只需要查看每个字符串的第一个字符来决定是否可以匹配第一个字符 ，如果是，则进行递归调用以检查字符串的其余部分。 当你在模式字符串中找到*时，诀窍将是知道该怎么做，因为它可能会或可能不会用于匹配s1中的第一个字符。 您不应该查看字符串的其余部分来决定要做什么。
由于这是家庭作业，我会留下你在那里发生的事情的详细信息，但希望这能让你思考正确的道路。
这是用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行代码，加上大括号）我可以发布 – 但我不确定你的消息是否想要给出算法，或只是指针。