用于将字符串与通配符模式匹配的递归函数 [英] Recursive function to match a string against a wildcard pattern

问题描述

所以我一直在努力解决这个任务，只是无法得到它。

So I've been trying to solve this assignment whole day, just can't get it.

以下函数接受2个字符串，第2个（不是第1个） ）可能包含 * 的（星号）。

* 是替代一个字符串（空，1个字符或更多），它可以出现（仅在s2中）一次，两次，更多或根本不显示，它不能与另一个 * 相邻（ ab ** c ），无需检查。

The following function accepts 2 strings, the 2nd (not 1st) possibly containing *'s (asterisks).
An * is a replacement for a string (empty, 1 char or more), it can appear appear (only in s2) once, twice, more or not at all, it cannot be adjacent to another * (ab**c), no need to check that.

public static boolean samePattern(String s1, String s2)

如果字符串具有相同的模式，则返回true 。

必须递归，不要使用任何循环，静态&全局变量。
可以使用局部变量&方法重载。

It returns true if strings are of the same pattern.
It must be recursive, not use any loops, static & global variables. Can use local variables & method overloading.

只能使用这些方法： charAt（i）， substring（i）， substring（i，j）， length（） 。

Can use only these methods: charAt(i), substring(i), substring(i, j), length().

示例：

1： TheExamIsEasy ; 2： * xamIs * y →true

1： TheExamIsEasy ; 2： Th * mIsEasy * →true

1： TheExamIsEasy ; 2： * →true

1： TheExamIsEasy ; 2： TheExamIsEasy →true

1： TheExamIsEasy ; 2： * IsHard →FALSE

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

我尝试使用<逐个比较字符code> charAt 直到遇到星号，然后通过比较是连续的char（ i + 1 ）检查星号是否为空星号）位置 i 的 s1 的字符，如果为真 - 继续递归 i +1 作为 s2的计数器& i 作为 s1的计数器;
如果为false则为
- 使用<$ c $继续递归c> i + 1 作为两者的计数器。

继续此操作，直到找到另一个星号或字符串结尾。

I tried comparing the the chars one by one using charAt until an asterisk is encountered, then check if the asterisk is an empty one by comparing is successive char (i+1) with the char of s1 at position i, if true -- continue recursion with i+1 as counter for s2 & i as counter for s1;
if false -- continue recursion with i+1 as counters for both.
Continue this until another asterisk is found or end of string.

我不知道，我的大脑失去了对事物的追踪，无法集中注意力，任何<强>指针/提示？我正朝着正确的方向前进吗？

I dunno, my brain loses track of things, can't concentrate, any pointers / hints? Am I in the right direction?

此外，有人告诉我们使用回溯技术来解决这个问题。

Also, it's been told that a backtracking technique is to be used to solve this.

到目前为止我的代码（即使在理论上也不起作用）：

My code so far (doesn't do the job, even theoretically):

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

推荐答案

这里有一些Pythonpsudocode这可能有帮助

Here's some Python "psudocode" that may help

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

以下是转换代码的粗略指南

Here is a rough guide for converting the code

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

这篇关于用于将字符串与通配符模式匹配的递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！