So lösen Sie das Wortmusterproblem im Go Java-Algorithmus

Wortmuster

Bestimmen Sie anhand eines Musters und einer Zeichenfolge s, ob s demselben Muster folgt.

Hier bezieht sich „folgen“ auf eine exakte Übereinstimmung. Beispielsweise besteht eine wechselseitige Verbindung zwischen jedem Buchstaben in „Muster“ und jedem nicht leeren Wort in der Zeichenfolge „s“.

• Beispiel 1:

Eingabe: Muster = "abba", s = " Hund Katze Katze Hund"

Ausgabe: wahr #

Eingabe: Muster = "abba", s = "Hund Katze Katze Fisch"

• Ausgabe : false

#🎜 🎜#

Beispiel 3:

Eingabe: Muster = " aaaa", s = "Hund Katze Katze Hund"

# 🎜🎜#Ausgabe: false

• Hinweis:

1 < ;= pattern.length <= 300

#🎜🎜 #pattern Enthält nur englische Kleinbuchstaben

1 <= s.length <= 3000

s Enthält nur englische Kleinbuchstaben und ' '#🎜🎜 #

s enthält keine führenden oder nachgestellten Leerzeichenpaare

# Jedes Wort in 🎜🎜#s wird durch ein einzelnes Leerzeichen getrennt

Methode 1: Hash-Tabelle (Java)# 🎜🎜#

In dieser Frage müssen wir feststellen, ob eine genaue Eins-zu-eins-Entsprechung zwischen Zeichen und Zeichenfolgen besteht. Das heißt, jedes Zeichen entspricht einer eindeutigen Zeichenfolge und jede Zeichenfolge entspricht nur einem Zeichen. In der Mengenlehre wird diese Beziehung „Bijektion“ genannt.

Um dieses Problem zu lösen, können wir eine Hash-Tabelle verwenden, um die jedem Zeichen entsprechende Zeichenfolge und die jeder Zeichenfolge entsprechenden Zeichen aufzuzeichnen. Dann zählen wir den Paarungsprozess jedes Zeichen- und Zeichenfolgenpaares auf und aktualisieren kontinuierlich die Hash-Tabelle. Wenn ein Konflikt auftritt, bedeutet dies, dass die gegebene Eingabe die Bijektionsbeziehung nicht erfüllt.

Die Frage fordert uns im Wesentlichen auf, zu bestimmen, ob die Zeichen in str den Zeichen im Muster eins zu eins entsprechen

Mit anderen Worten, die gleichen Zeichen im Muster sollten auch übereinstimmen in str sein Gleiches gilt, verschiedene Zeichen sollten auch in str unterschiedlich sein

Wir können die erste Vorkommensposition jedes Zeichens im Muster über ein Wörterbuch aufzeichnen, das heißt dict[x]=pattern.index(x ). Dann durchlaufen wir jeden Buchstaben im Muster,

, merken uns i als den aktuell durchlaufenen Index

, dann ist dict[pattern[i]] das Zeichenmuster[i] in Muster Der vorherige Index

Bestimmen Sie, ob die Buchstaben, die den beiden Indizes in str entsprechen, gleich sind. Wenn sie unterschiedlich sind, geben Sie False zurück

class Solution {
    public boolean wordPattern(String pattern, String str) {
        Map<String, Character> str2ch = new HashMap<String, Character>();
        Map<Character, String> ch3str = new HashMap<Character, String>();
        int m = str.length();
        int i = 0;
        for (int p = 0; p < pattern.length(); ++p) {
            char ch = pattern.charAt(p);
            if (i >= m) {
                return false;
            }
            int j = i;
            while (j < m && str.charAt(j) != &#39; &#39;) {
                j++;
            }
            String tmp = str.substring(i, j);
            if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) {
                return false;
            }
            if (ch3str.containsKey(ch) && !tmp.equals(ch3str.get(ch))) {
                return false;
            }
            str2ch.put(tmp, ch);
            ch3str.put(ch, tmp);
            i = j + 1;
        }
        return i >= m;
    }
}

Zeitkomplexität: O(n+ m)# 🎜🎜#

Raumkomplexität: O(n+m)

Methode 1: Hash-Tabelle (GO)

Die konkreten Methodenideen stehen bereits oben Im Text ausgedrückt finden Sie Einzelheiten im obigen Inhalt

Spezifische Methode:

pattern = "abba", konvertiert in 0110

#🎜 🎜#str = „Hund, Katze, Katze, Hund“, umgewandelt in 0110

func wordPattern(pattern string, str string) bool {
    p := strings.Split(pattern,"")
    s := strings.Split(str," ")
    if len(p) != len(s) {
        return false
    }
    pNum,sNum := 0,0
    pString,sString := "",""
    pMap := map[string]int{}
    sMap := map[string]int{}
    for _,v := range p {
        if _,ok := pMap[v];ok{
            pString += strconv.Itoa(pMap[v])
        }else{
            pString += strconv.Itoa(pNum)
            pMap[v] = pNum
            pNum++
        }
    }
    for _,v := range s {
        if _,ok := sMap[v];ok{
            sString += strconv.Itoa(sMap[v])
        }else{
            sString += strconv.Itoa(sNum)
            sMap[v] = sNum
            sNum++
        }
    }
    if pString == sString {
        return true
    }
    return false
}

Zeitkomplexität: O(n+m)

Raumkomplexität: O(n+ m）

Das obige ist der detaillierte Inhalt vonSo lösen Sie das Wortmusterproblem im Go Java-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!