Comment résoudre le problème des chaînes entrelacées dans l’algorithme Go Java ?

Chaînes entrelacées

Étant donné trois chaînes s1, s2, s3, veuillez aider à vérifier si s3 est composé de s1 et s2 entrelacés.

La définition et le processus d'entrelacement de deux chaînes s et t sont les suivants, où chaque chaîne sera divisée en plusieurs sous-chaînes non vides :

s = s1 + s2 + ... + sn

t = t1 + t2 + ... + tm

|n - m| + ...

Remarque : a + b signifie que les chaînes a et b sont concaténées.

Exemple 1 :

Entrée : s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

Sortie : true

Exemple 2 :

Entrez : s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

Sortie : false

Exemple 3 :

Entrée : s1 = "", s2 = "", s3 = ""

Sortie : true

Invite :

0 <= s1.length, s2.length <= 100

0 <= s3.length <= 200

s1, s2 et s3 sont le tout Composé de lettres anglaises minuscules

Méthode 1 : Programmation dynamique (Java)

Équation d'état :

Limite 1 : dp[0][0] = true ;

Limite 2 : si i=0 : dp[ 0 ]dp[j] = s2[0-j) est égal à s3[0,j) Lorsque false est rencontré, vous pouvez directement omettre

Limite 3 : si j=0 : dp[i]dp[0] = s1[ 0-i ) est égal à s3[0,i) Vous pouvez l'omettre directement après avoir rencontré false

Dans d'autres cas, atteindre (i, j) peut aller de (i-1,j) à l'étape suivante, et sélectionner s1[ i-1] pour arriver ; il peut également être atteint en faisant un pas vers la droite depuis (i,j-1) et en sélectionnant s2[j-1] ; 1][j] &&s3[i+j-1] == s1[i-1]) || (dp[i][j-1] && s3[i+j-1] == s2[j-1 ])

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length(), t = s3.length();
        if (n + m != t) {
            return false;
        }
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0][0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[i][j] = f[i][j] || (f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));
                }
                if (j > 0) {
                    f[i][j] = f[i][j] || (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));
                }
            }
        }
        return f[n][m];
    }
}

Complexité temporelle : O(m *n)

Complexité spatiale : O(m*n)

Méthode 1 : Programmation dynamique (GO)

La méthode spécifique a été décrite ci-dessus, veuillez consulter ce qui précède contenu pour plus de détails.

dp[i][j] signifie si les premiers i caractères de s1 et les j premiers caractères de s2 peuvent former les premiers i+j caractères de s3. Si c'est le cas, remplissez la chaîne. Sinon, c'est un vide. string.

Équation de transition d'état : La partie supérieure n'est pas une chaîne vide et le caractère actuel de s1 est égal au caractère actuel de s3, alors la chaîne est égale à la chaîne supérieure + le côté gauche du caractère actuel de s1. n'est pas une chaîne vide et le caractère actuel de s2 est égal au caractère actuel de s3, alors la chaîne est égale au caractère de gauche Chaîne + caractère actuel de s2

func isInterleave(s1 string, s2 string, s3 string) bool {
    m, n := len(s1), len(s2)
    if m + n != len(s3) { //长度不等肯定不能组成
        return false
    }
    dp := make([][]string, m+1) //dp[i][j]含义为s1的前i个字符，s2前j个字符，能否组成s3前i+j个字符，能的话填写字符串
    for i:=0; i<=m; i++ {
        dp[i] = make([]string, n+1)
    }
    for i:=1; i<=m; i++ { //s2字符串为空的情况
        if s1[:i] == s3[:i] {
            dp[i][0] = s1[:i]
        }
    }
    for i:=1; i<=n; i++ { //s1字符串为空的情况
        if s2[:i] == s3[:i] {
            dp[0][i] = s2[:i]
        }
    }
    for i:=1; i<=m; i++ {
        for j:=1; j<=n; j++ {
            if dp[i-1][j] != "" && s1[i-1] == s3[i+j-1] { //上方字符串符合并且s1当前字符和s3字符相等，
                dp[i][j] = dp[i-1][j] + string(s1[i-1])   //则当前状态等于上方字符串+s1当前字符
            }
            if dp[i][j-1] != "" && s2[j-1] == s3[i+j-1] { //左侧字符串符合并且s2当前字符和s3字符相等
                dp[i][j] = dp[i][j-1] + string(s2[j-1])   //则当前状态等于左侧字符串+s2当前字符
            }
        }
    }
    if dp[m][n] == s3 { //右下角字符串是否等于s3，等于则能合并出，否则不能
        return true
    }
    return false
}

Complexité temporelle : O(m*n)

Complexité spatiale : O(m*n)

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!