5

私は最近、ソフトウェア エンジニアリングの職について 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 分以内に結論を出すことができませんでした。

この問題を迅速かつ効率的に解決する方法を教えてください。

どうもありがとう！

4

2 に答える 2

6

正規表現の使用が許可されていると仮定すると、次のように記述できます。

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

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

"^"は文字列の始まりです文字列
"$"の終わりは
.「任意の文字」の場合、1回だけ
.*は「任意の文字」の場合、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 に答える