Comment résoudre le problème de modèle de mot dans l'algorithme Go Java

Modèle de mot

Étant donné un motif motif et une chaîne s, déterminez si s suit le même motif.

"Suivre" fait ici référence à une correspondance exacte. Par exemple, il existe une connexion bidirectionnelle entre chaque lettre du motif et chaque mot non vide de la chaîne s.

• Example 1:

input: motif = "abba", s = "chien chat chat chien"

output: true

• example 2:

input: motif = "abba", s = "chien chat chat poisson"

Sortie : false

• Exemple 3 :

Entrée : motif = "aaaa", s = "chien chat chat chien"

Sortie : false

Astuce :

1 <= pattern.length <= 300

le motif ne contient que des lettres anglaises minuscules

1 <= s.length <= 3000

s ne contient que des lettres anglaises minuscules et ' '

s ne contiennent aucune paire d'espaces de début ou de fin

s Chaque mot est séparé par un seul espace

Méthode 1 : Table de hachage (Java)

Dans cette question, nous devons juger les caractères et les chaînes S'il existe une correspondance individuelle entre eux. Autrement dit, tout caractère correspond à une chaîne unique et toute chaîne correspond à un seul caractère. En théorie des ensembles, cette relation est appelée « bijection ».

Pour résoudre ce problème, nous pouvons utiliser une table de hachage pour enregistrer la chaîne correspondant à chaque caractère et les caractères correspondant à chaque chaîne. Ensuite, nous énumérons le processus d'appariement de chaque paire de caractères et de chaînes et mettons continuellement à jour la table de hachage. Si un conflit se produit, cela signifie que l'entrée donnée ne satisfait pas à la relation de bijection.

La question nous demande essentiellement de déterminer si les caractères de str correspondent un à un aux caractères de pattern

C'est-à-dire que les mêmes caractères de pattern devraient également être les mêmes dans str, et différents caractères devraient également être différent dans str

Nous pouvons enregistrer la première position d'occurrence de chaque caractère dans le modèle via un dictionnaire, c'est-à-dire dict[x]=pattern.index(x). Ensuite, nous parcourons chaque lettre du motif,

Rappelez-vous i comme index actuellement parcouru

Ensuite, dict[motif[i]] est l'index précédent du motif de caractère[i] dans pattern

Jugez les deux index dans str Si les lettres correspondantes sont les mêmes, sinon, retournez False

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

Complexité temporelle : O(n+m)

Complexité spatiale : O(n+m)

Méthode 1 : Table de hachage (GO)

La méthode spécifique et le contenu de l'idée a été indiqué ci-dessus. Veuillez consulter le contenu ci-dessus pour plus de détails

Méthode spécifique :

pattern = "abba", converti en 0110

str = "dog cat cat dog", converti en 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
}

.

Complexité temporelle : O(n+m)

Complexité spatiale : O(n+m)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!