文字列が特定のパターンを満たしているかどうかを調べる

Question

最近、私はGoogleとソフトウェアエンジニアリングの面談を行いました。

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 

だからコールは

のようなものが考えられます。

givenPatternが含まれている文字列です：

だから、あなたは次のことを行い

boolean isPattern(String givenPattern, String stringToMatch) 

機能を構築する必要が

isPattern("abc", "abcd") - それはdとしてfalseを返します。私たちは「」開始時に、それが「BC」

isPattern("a?bc", "adbc") trueを返しに多くの文字を終了した後、持っているとして、OESパターンに一致しない事実である

isPattern("a*bc", "aksakwjahwhajahbcdbc")、（「d」は余分です）パターンの各文字が指定された文字列内で一致するためです。

インタビュー中に、私はパターンを歩き回ることができると思った。文字が文字かa *か？与えられた文字列の文字をそれぞれ一致させます。しかし、それはループの複雑なセットで終わったし、45分以内に結論に至ることはできなかった。

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

多くの感謝！

Answer 1

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

（再帰を理解するのが最も簡単であること。）

Answer 2

はあなたのような何かを書かれている可能性があり、正規表現を使用することを許可されていると仮定すると：

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

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

"^"が文字列
"$"の始まりである
.「は、任意の文字のための文字列の終わりです"、一度だけ
.*は"任意の文字 "のもので、0回以上です

注：0123を制限したい場合文字にと?を入力すると、.の代わりに[a-zA-Z]を使用できます。