Wie löst man das Problem der verschachtelten Zeichenfolge im Go Java-Algorithmus?

Interlaced string

Anhand der drei Zeichenfolgen s1, s2, s3 helfen Sie bitte bei der Überprüfung, ob s3 aus verschachtelten S1 und S2 besteht.

Die Definition und der Prozess der Verschachtelung zweier Zeichenfolgen s und t sind wie folgt, wobei jede Zeichenfolge in mehrere nicht leere Teilzeichenfolgen unterteilt wird:

s = s1 + s2 + ... + sn

t = t1 + t2 + ... + tm

|n - m|. <= 1

# 🎜🎜#Die Verschachtelung ist s1 + t1 + s2 + t2 + s3 + t3 + ... oder t1 + s1 + t2 + s2 + t3 + s3 + ...

Hinweis :a + b bedeutet, dass die Zeichenfolgen a und b verkettet sind.

• Beispiel 1:

Eingabe: s1 = "aabcc", s2 = " dbbca", s3 = "aadbbcbcac"

Ausgabe: true

• Beispiel 2:

Eingabe: s1 = „aabcc“, s2 = „dbbca“, s3 = „aadbbbacc“

Ausgabe: false

• Beispiel 3:

Eingabe: s1 = "", s2 = "", s3 = " "

Ausgabe: wahr

Eingabeaufforderung:

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

# 🎜🎜#0 <= s3.length <= 200

s1, s2 und s3 bestehen alle aus englischen Kleinbuchstaben

Methode 1: Dynamische Planung (Java)

Zustandsgleichung:

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

Grenze 2: wenn i=0: dp[0]dp[j] = s2[0-j) gleich s3[0,j) Wenn „false“ auftritt, können Sie es direkt weglassen

Grenze 3 : wenn j=0 : dp[i]dp[0] = s1[0-i) gleich s3[0,i) Wenn false auftritt, kann es direkt weggelassen werden

In anderen Fällen, Das Erreichen von (i, j) kann erfolgen, indem (i-1,j) auf den nächsten Schritt zeigt und s1[i-1] auswählt. Es ist auch möglich, (i,j-1) nach rechts zu zeigen und auszuwählen s2[j-1] ankommen;

#🎜 🎜#dp[i,j] = (dp[i-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];
    }
}

Zeitkomplexität: O(m *n)

Raumkomplexität :O(m*n)

Methode 1: Dynamische Programmierung (GO)

Die spezifische Methode wurde angegeben Weitere Informationen finden Sie im obigen Inhalt.

dp[i][j] bedeutet die ersten i Zeichen von s1, die ersten j Zeichen von s2, ob sie die ersten i+j Zeichen von s3 bilden können, wenn ja, füllen Sie die Zeichenfolge aus , wenn nicht, ist es ein leeres Zeichen String

Zustandsübergangsgleichung: Der obere Teil ist kein leerer String und das aktuelle Zeichen von s1 ist gleich dem aktuellen Zeichen von s3, dann ist die Zeichenfolge gleich zur oberen Zeichenfolge + dem aktuellen Zeichen von s1. Die linke Seite ist keine leere Zeichenfolge und das aktuelle Zeichen von s2 ist gleich dem aktuellen Zeichen von s3, dann ist die Zeichenfolge gleich der linken Zeichenfolge + dem aktuellen Zeichen von 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
}

Zeitkomplexität: O(m*n)

Raumkomplexität: O( m*n）

Das obige ist der detaillierte Inhalt vonWie löst man das Problem der verschachtelten Zeichenfolge im Go Java-Algorithmus?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!