Rekursiver Vergleich von Textmuster und Text

[kokoli]

Bitte um Hilfe:
Man soll überprüfen ob ein Textmuster und ein Text zusammenpasst. Im Textmuster steht der Stern * als Platzhaltersymbol für eine beliebige Anzahl beliebiger Zeichen.
Beispiele:
Textmuster "abc" und Text "abc" passen zusammen.
Textmuster "*" und Text "" passen zusammen.
Textmuster "*c" und Text "abc" passen zusammen.
Textmuster "a*c*e" und Text "abcde" passen zusammen.
Textmuster "abc" und Text "ab" passen nicht zusammen.
Textmuster "a*" und Text "bcd" passen nicht zusammen.

Platzhaltersymbol * darf beliebig oft vorkommen.
boolean isMatching(String pattern, String string), die true zurückgibt, wenn Textmuster pattern und Text string zusammenpassen und sonst false.
Das ist gegeben:

static char[] pArray;
static char[] sArray;

public static boolean M(/* Parameter */) {

return true;
}

public static boolean isMatching(String pattern, String string) {

pArray = (pattern + ".").toCharArray();
sArray = (string + ".").toCharArray();

return M(/* Parameter */);
}


Main Methode ist gegeben.

 

[Gelöschtes Mitglied 65838]

public static void main(String[] args) {
        String patternString = createRegexFromGlob("abc*");
        List<String> list = Arrays.asList("abf", "abc_fgh", "abcgafa", "fgabcafa");
        list.forEach(it -> System.out.println(it.matches(patternString)));
}

private static String createRegexFromGlob(String glob) {
    StringBuilder out = new StringBuilder("^");
    for(int i = 0; i < glob.length(); ++i) {
        final char c = glob.charAt(i);
        switch(c) {
            case '*': out.append(".*"); break;
            case '?': out.append('.'); break;
            case '.': out.append("\\."); break;
            case '\\': out.append("\\\\"); break;
            default: out.append(c);
        }
    }
    out.append('$');
    return out.toString();
}

 

[fhoffmann]

Es ist natürlich möglich, dies - wie @Joreyk es getan hat - mit Hilfe von regulären Ausdrücken zu lösen.
Ich gehe aber davon aus, dass ihr das ohne solche Hilfsmittel lösen sollt.

Als Parameter vom M würde ich die Positionen in beiden Arrays übergeben, bis zu denen ich schon gearbeitet habe, also

public static boolean M(int pPos, int sPos)

Gestartet wird es dann mit M(0, 0)

Sollte pArray[pPos] ein Buchstabe stehen, so überprüft man, ob in sArray[sPos] der gleiche Buchstabe steht. Ist dies der Fall, ruft man M(pPos+1, sPos+1) auf. Ansonsten gibt man false zurück.

Sollte pArray[pPos] jedoch ein Stern stehen, so muss man für alle möglichen folgenden Stellen im sArray überprüfen, ob der Rest passt, also in einer for-Schleife abfragen, ob M(pPos+1, i).
Ist dies für ein i der Fall, so gibt man true zurück, ansonsten gibt man false zurück.

Bei allem muss man ggf. dafür sorgen, dass man keine ArrayIndexOutOfBounds-Exception bekommt.
Möglicherweise muss man auch den Punkt (als Endezeichen) gesondert behandeln.

Soweit ein paar Tipps, ohne dir gleich die ganze Lösung zu verraten.