Go Java アルゴリズムでインターリーブ文字列の問題を解決するにはどうすればよいですか?

インターリーブ文字列

3 つの文字列 s1、s2、s3 がある場合、s3 がインターリーブされた s1 と s2 で構成されているかどうかを確認してください。

2 つの文字列 s と t をインターリーブする定義とプロセスは次のとおりです。各文字列はいくつかの空ではない部分文字列に分割されます:

s = s1 s2 .. sn

t = t1 t2 ... tm

|n - m|

千鳥配置は s1 t1 s2 t2 s3 t3 ... または t1 s1 t2 s2 t3 s3 ...

注: a b は、文字列 a と b の連結を意味します。

• 例 1:

入力: s1 = "aabcc"、s2 = "dbbca"、s3 = "aadbbcbcac"

出力: true

• 例 2:

入力: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

出力: false

• 例 3:

##入力: s1 = ""、s2 = ""、s3 = ""

出力: true

プロンプト:

0

0 <= s3.length <= 200

s1、s2、および s3 はすべて小文字の英字で構成されます

# # 方法 1: 動的プログラミング (Java)

状態方程式:

境界 1: dp[0][0] = true;

境界 2: if i =0 : dp[0]dp[j] = s2[0-j) と等しい s3[0,j) false が見つかった場合は、

境界 3: if j=0 : dp を直接省略できます。 [i] dp[0] = s1[0-i) = s3[0,i) false が見つかった場合は、後で直接省略できます。

他の場合には、(i, j) に到達するのは次のとおりです。 (i-1,j) から次のステップに進み、s1[i-1] を選択して到着します。(i,j-1) から右に 1 ステップ進み、s2[j-1] を選択して到着することもできます。 ;

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

時間計算量: O(m*n)

空間計算量: O(m *n)

方法 1: 動的プログラミング (GO)

具体的な方法は上記で説明しました。詳細については、上記のコンテンツを参照してください。

dp[i][j] は、s1 の最初の i 文字、s2 の最初の j 文字、s3 の最初の i j 文字を形成できるかどうか、形成できる場合は文字列を埋める、そうでない場合は文字列を意味します。それは空の文字列です

状態伝達方程式: 上部が空の文字列ではなく、s1 の現在の文字が s3 の現在の文字と等しい場合、文字列は上部の文字列と等しいです。 s1 の現在の文字の左側が空の文字列ではなく、s2 の現在の文字が s3 の現在の文字と等しい場合、文字列は左側の文字列 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
}

時間計算量: O (m*n)

空間計算量: O (m*n)

以上がGo Java アルゴリズムでインターリーブ文字列の問題を解決するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。