代码之家 › 专栏 › 技术社区 › George Kagan

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

backtracking wildcard recursion string java

George Kagan · 技术社区 · 16 年前

所以我一整天都在努力解决这项任务,但都做不到。

以下函数接受两个字符串,第二个(不是第一个)可能包含 * (星号)。
安 * 是字符串(空、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: 考试容易 2; Th*mIsEasy* 爱尔实
1: 考试容易 2; * 爱尔实
1: 考试容易 2; 考试容易 爱尔实
1: 考试容易 2; The*IsHard 假错误

我试着用 charAt 在遇到星号之前,通过比较“是连续字符”来检查星号是否为空。( i+1 )以…为特征 s1 就位 i ,如果为true--继续递归 I+ 1 作为计数器 s2 和; 我 作为计数器 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);
}

4 回复 | 直到 9 年前

John La Rooy 10 年前

这里有一些可以帮助您的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

Paul Kuliniewicz 16 年前

您当前的方法的问题是,它不考虑*可以匹配的所有可能的子字符串。例如,samepattern(“a b a b a b a b a b a b”,“a*b”)应返回true;除了字符串的第一个字母和最后一个字母外,*可以匹配所有字母,但您的代码假定,由于以下字母是b,*匹配空字符串。

我建议在寻找匹配项时将samepattern视为“消费”它的两个输入字符串。在每个步骤中,Samepattern只需查看每个字符串的第一个字符就可以决定是否匹配 在第一个字符 可以,如果可以,则进行递归调用以检查字符串的其余部分。诀窍是知道当您在模式字符串中达到*时要做什么,因为它可能用于或不用于匹配s1中的第一个字符。您不需要查看字符串的其余部分来决定要做什么。

既然这是家庭作业,我就不去想那些发生在你身上的细节了,但希望这能让你走上正确的道路。

Tomek Tarczynski 16 年前

这是用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;
    }

Andrew Anderson 16 年前

在处理这样的算法时,把问题分成小块在你的头脑中通常是值得的。

因为您是字符串解析,所以需要逐个字符地考虑解决方案。此外,由于您无法控制这些字符串的实际大小,因此在任何给定的时间限制自己只考虑字符串的第一个字符。(嗯-有一个例外)

一旦你确定你要处理的角色需要进一步调查字符串的其余部分, 把它们扔掉 把它们放在身边只会增加复杂性,那么为什么要麻烦呢?(相反,如果字符完全不匹配,您就完成了-对吗?)

当然,这是一个递归字符串,所以您必须有几个条件来控制失败/成功,这些条件处理字符串的整体状态——但这些并不是问题的核心——检查函数顶部字符串的状态,然后继续。

我有一个算法,我挑起(11行代码,加上大括号),我可以张贴如果你想要一个完整的解决方案-但我不确定你的消息,如果你想得到算法,或只是指针。