Sprawdzanie, czy ciąg znaków spełnia określony wzorzec.

Question

Niedawno przeprowadziłem wywiad z Google w sprawie stanowiska inżynierii oprogramowania i zadałem pytanie dotyczące budowania wzornika wzorów.

Więc trzeba zbudować funkcji

boolean isPattern(String givenPattern, String stringToMatch) 

który wykonuje następujące czynności:

givenPattern jest ciąg znaków, który zawiera:

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 

więc wywołanie może być coś podobnego

isPattern("abc", "abcd") - zwraca wartość false, ponieważ OES nie pasuje do wzorca („d” jest extra)

isPattern("a*bc", "aksakwjahwhajahbcdbc"), co jest prawdą, jak mamy „a” na początku, wiele znaków po czym kończy się „BC”

isPattern("a?bc", "adbc") zwraca true ponieważ każdy znak wzoru pasuje do danego ciągu znaków.

Podczas rozmowy, czas jest krótki, pomyślałem, można przejść przez wzór, sprawdzić, czy znak jest literą, a * lub grupę? a następnie dopasuj odpowiednio znaki w danym ciągu. Ale to okazało się skomplikowanym zestawem pętli for-loop i nie udało nam się dojść do skutku w ciągu 45 minut.

Czy ktoś mógłby mi powiedzieć, jak szybko i skutecznie rozwiązać ten problem?

Wielkie dzięki!

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

(Rekurencja jest najłatwiejsze do zrozumienia.)

Answer 2

Zakładając, że mogą korzystać z regexes, można napisać coś takiego:

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

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

"^" jest początkiem łańcucha
"$" jest koniec łańcucha
. jest dla „dowolny znak ", dokładnie jeden raz:
jest dla" dowolnego znaku ", 0 lub więcej razy

Uwaga: jeśli chcesz ograniczyć * i ? tylko do liter, możesz użyć [a-zA-Z] zamiast ..