查找字符串是否符合某种模式

Question

我最近接受了Google对软件工程职位的采访,并且问到了构建模式匹配器的问题.

所以你必须建立

boolean isPattern(String givenPattern, String stringToMatch)

执行以下操作的功能:

givenPattern 是一个字符串,包含:

a) 'a'-'z' chars
b) '*' chars which can be matched by 0 or more letters
c) '?' which just matches to a character - any letter basically

所以电话会是这样的

isPattern("abc", "abcd") - 返回false,因为它与模式不匹配('d'是额外的)

isPattern("a*bc", "aksakwjahwhajahbcdbc"),这是真的,因为我们在开始时有一个'a',之后有很多字符然后以"bc"结尾

isPattern("a?bc", "adbc") 当模式的每个字符在给定字符串中匹配时返回true.

在采访中,时间很短,我想可以走过模式,看一个角色是一个字母,一个*或一个？然后分别匹配给定字符串中的字符.但最终成为一组复杂的for循环,我们无法在给定的45分钟内得出结论.

有人可以告诉我他们如何快速有效地解决这个问题？

非常感谢!

Answer 1

假设您被允许使用正则表达式,您可以编写如下内容:

static boolean isPattern(String givenPattern, String stringToMatch) {
    String regex = "^" + givenPattern.replace("*", ".*").replace("?", ".") + "$";

    return Pattern.compile(regex).matcher(stringToMatch).matches();
}

"^"是字符串的开头是字符串
"$"的结尾
.是"任何字符",一次
.*是"任何字符",0或更多次

注意:如果您想限制*和?仅限字母,您可以使用[a-zA-Z]而不是..

Answer 2

boolean isPattern(String givenPattern, String stringToMatch) {
    if (givenPattern.empty)
        return stringToMatch.isEmpty();
    char patternCh = givenPatter.charAt(0);
    boolean atEnd = stringToMatch.isEmpty();
    if (patternCh == '*') {
        return isPattenn(givenPattern.substring(1), stringToMatch)
            || (!atEnd && isPattern(givenPattern, stringToMatch.substring(1)));
    } else if (patternCh == '?') {
        return !atEnd && isPattern(givenPattern.substring(1), 
            stringToMatch.substring(1));
    }
    return !atEnd && patternCh == stringToMatch.charAt(0)
          && isPattern(givenPattern.substring(1), stringToNatch.subtring(1);
}

（递归是最容易理解的。）