5

我最近接受了谷歌软件工程职位的面试，问题是关于构建模式匹配器。

所以你必须建立

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 分钟内得出结论。

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

非常感谢！

4

2 回答 2

6

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

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

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

"^"是字符串的开头是字符串
"$"的结尾
.是“任何字符”，恰好一次
.*是“任何字符”，0次或更多次

注意：如果您只想将*和限制?为字母，您可以使用[a-zA-Z]代替.。

于 2013-01-25T13:53:46.883 回答
3 
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);
}

（递归最容易理解。）

于 2013-01-25T14:01:03.523 回答