2010-06-06 10 views
8

So habe ich versucht, diese Aufgabe den ganzen Tag zu lösen, kann es einfach nicht bekommen.Rekursive Funktion, um eine Zeichenfolge mit einem Platzhaltermuster zu vergleichen

Die folgende Funktion akzeptiert 2 Strings, die zweite (nicht die erste) möglicherweise enthält * 's (Sternchen).
Ein * ist ein Ersatz für eine Zeichenfolge (leer, 1 Zeichen oder mehr), kann erscheinen (nur in s2) einmal, zweimal, mehr oder gar nicht, es kann nicht neben einem anderen sein * (ab**c), nein muss das überprüfen.

public static boolean samePattern(String s1, String s2) 

Es gibt True zurück, wenn Strings das gleiche Muster haben.
Es muss rekursiv sein, keine Schleifen verwenden, statische & globale Variablen. Kann lokale Variablen & Methode Überladung verwenden.

Kann nur diese Methoden verwenden: charAt(i), substring(i), substring(i, j), length().

Beispiele:

1: TheExamIsEasy; 2: The*xamIs*y → richtig
1: TheExamIsEasy; 2: Th*mIsEasy* → richtig
1: TheExamIsEasy; 2: * → wahr
1: TheExamIsEasy; 2: TheExamIsEasy → wahr
1: TheExamIsEasy; 2: The*IsHard → FALSE

habe ich versucht, die die Zeichen eines nach dem anderen zu vergleichen charAt verwenden, bis ein Stern angetroffen wird, dann prüfen, ob der Stern eine leere ist, sukzessive durch den Vergleich char (i+1) mit dem char von s1 an Position i, falls wahr - Fortsetzung der Rekursion mit i+1 als Zähler für s2 & i als Zähler für s1;
wenn falsch - Fortsetzung der Rekursion mit i+1 als Zähler für beide.
Fahren Sie fort, bis ein anderes Sternchen gefunden wird oder das Ende der Zeichenfolge.

Ich weiß nicht, mein Gehirn verliert die Spur der Dinge, kann sich nicht konzentrieren, keine Zeiger/Hinweise? Bin ich in die richtige Richtung?

Es wurde auch gesagt, dass eine Backtracking Technik verwendet werden soll, um dies zu lösen.

Mein Code bisher (nicht die Arbeit erledigen, auch theoretisch):

public static boolean samePattern(String s1, String s2) { 
    if (s1.equals(s2) || s2 == "*") { 
     return true; 
    } 
    return samePattern(s1, s2, 1); 
} 
public static boolean samePattern(String s1, String s2, int i) 
{ 
    if (s1.equals(s2)) 
     return true; 
    if (i == s2.length() - 1) // No *'s found -- not same pattern. 
     return false; 

    if (s1.substring(0, i).equals(s2.substring(0, i))) 
     samePattern(s1, s2, i+1); 
    else if (s2.charAt(i-1) == '*') 
     samePattern(s1.substring(0, i-1), s2.substring(0, i), 1); // new smaller strings. 
    else 
     samePattern(s1.substring(1), s2, i); 
} 
+2

Kudos für die Umwandlung, und nicht die gesamte Lösung. –

Antwort

4

Hier einige Python „psudocode“, die

def samePattern(s1,s2): 
    if s2 == "*" or s1 == s2: return True 
    if s1 == "": return False 
    if s1[0] == s2[0]: return samePattern(s1[1:], s2[1:]) 
    if s2[0] == "*": return samePattern(s1, s2[1:]) or samePattern(s1[1:], s2) 
    return False 

Hier ist eine grobe Orientierung ist helfen kann Vorschläge für Fragen an den Code

s[0] = the first character 
s[1:] = the string minus the first character 
+0

Ist die 's2 == "*" 'in das erste 'if' wirklich notwendig? Und sollten Sie nicht überprüfen, ob' s2' länger ist als 's1' (zB in Ihrem zweiten wenn)? – strager

+0

@strager, ja es ist notwendig mit dem Weg den Rest des Codes ist geschrieben. –

+0

Vielen Dank! Danke an alle anderen auch, ich verstehe jetzt. :) –

2

Hier Probenlösung in C# geschrieben. Entschuldigung für fehlende Kommentare, aber ich hatte keine Zeit für sie:/Wenn Sie sie morgen noch brauchen, dann kann ich etwas schreiben, aber ich hoffe, Sie werden die Idee greifen.

public static bool CompareString(string s1, string s2, bool wildCard) 
{ 
     // Both strings are empty 
     if ((s1.Length == 0) && (s2.Length == 0)) return true; 

     // Second string is empty and there is wildCard character 
     if (s2.Length == 0 && wildCard) return true; 

     //First string is empty. Answer will be true only if all characters in second string are *. 
     if (s1.Length == 0 && s2.Length > 0 && s2[0] == '*') 
     { 
      string newS2 = s2.Remove(0, 1); 
      return CompareString(s1, newS2, true); 
     } 

     // One of the strings is empty, and second one is not. 
     if (s1.Length * s2.Length == 0) return false; 

     if (wildCard) 
     { 
      string newS1 = s1.Remove(0, 1); 
      if (CompareString(newS1,s2,true) || CompareString(newS1,s2,false)) 
      { 
       return true; 
      } 
     } 
     else 
     { 
      if (s2[0] == '*') 
      { 
       string newS2 = s2.Remove(0,1); 
       if (CompareString(s1,newS2,true) || CompareString(s1,newS2,false)) 
       { 
        return true; 
       } 
      } 
      else 
      { 
       if (s1[0] == s2[0]) 
       { 
        string newS1 = s1.Remove(0,1); 
        string newS2 = s2.Remove(0,1); 
        return CompareString(newS1,newS2,false); 
       } 
       else 
       { 
        return false; 
       } 
      } 
     } 
     return false; 
    } 
+0

Eine Hilfsmethode, die ein "Wildcard" -Flag enthält, ist nicht erforderlich - Sie können dies in weniger Code ohne durchführen. –

5

Das Problem mit Ihrem aktuellen Ansatz ist, dass es nicht alle möglichen Teilstrings berücksichtigt, die ein * zusammenbringen kann. Zum Beispiel sollte samePattern ("ababababab", "a * b") wahr zurückgeben; Das * kann alle außer dem ersten und letzten Buchstaben der Zeichenfolge enthalten, aber Ihr Code geht davon aus, dass das * mit der leeren Zeichenfolge übereinstimmt, da der folgende Buchstabe b ist.

Ich schlage vor, samePattern als "konsumieren" seine zwei Eingabezeichenfolgen, wie es nach einer Übereinstimmung sucht. Bei jedem Schritt sollte samePattern nur das erste Zeichen jeder Zeichenfolge prüfen, um zu entscheiden, ob eine Übereinstimmung beim ersten Zeichen möglich ist, und wenn dies der Fall ist, einen rekursiven Aufruf durchführen, um den Rest der Zeichenfolge zu überprüfen. Der Trick wird sein zu wissen, was zu tun ist, wenn Sie ein * in der Musterzeichenfolge erreichen, da es möglicherweise verwendet wird, um das erste Zeichen in s1 anzupassen. Sie sollten nicht den Rest der Zeichenfolge betrachten müssen, um zu entscheiden, was zu tun ist.

Da dies Hausaufgaben sind, werde ich die Details dessen, was dort passiert, herausfinden, aber hoffentlich bringt dich das auf den richtigen Weg.

+1

Yup; Verwenden Sie Rekursion, um eine reduzierte, einfachere Eingabe zu verarbeiten. – strager

2

Wenn es um Algorithmen wie diese geht, lohnt es sich oft, das Problem in kleine Stücke im Kopf zu zerlegen.

Da Sie ein String-Parsing durchführen, sollten Sie die Lösung Zeichen für Zeichen betrachten. Da Sie keine Kontrolle über die tatsächliche Größe dieser Zeichenfolgen haben, beschränken Sie sich darauf, immer nur das erste Zeichen der Zeichenfolge zu berücksichtigen. (Na ja - mit einer Ausnahme)

Sobald Sie festgestellt haben, dass die Charaktere Sie mit Warrant weiteren Untersuchungen in den Rest der Zeichenfolge handeln, werfen sie weg; sie herumzuhalten erhöht nur die Komplexität, warum also die Mühe machen? (Umgekehrt, wenn die Zeichen nicht übereinstimmen, sind Sie fertig - richtig?)

Natürlich ist dies eine Rekursion auf Strings, so dass Sie eine Reihe von Bedingungen für den Erfolg haben müssen Der Gesamtzustand der Strings - aber das sind nicht das Problem - überprüfen Sie den Zustand der Zeichenfolge an der Spitze Ihrer Funktion, und fahren Sie fort.

Ich habe einen Algorithmus, den ich aufgepeitscht habe (11 Zeilen Code plus Klammern), den ich posten kann, wenn Sie eine vollständige Lösung wünschen - aber ich war nicht sicher durch Ihre Nachricht, wenn Sie den Algorithmus erhalten wollten, oder nur Zeiger.

+0

Hinweis zu sich selbst: Fange nicht an, eine Antwort zu tippen, werde abgelenkt und beende dann deine Antwort, ohne in der Zwischenzeit nach Updates zu suchen. Ich habe viel über Paul Kuliniewicz geschrieben. :(Ich lasse das hier für den Fall, dass etwas in, wie ich Dinge schrieb, mit dem OP resoniert. –

+0

Das macht Ihre Antwort nicht weniger gültig oder hilfreich. =] – strager

Verwandte Themen