Bagaimana untuk menyelesaikan masalah rentetan interleaved dalam algoritma Go Java?

Rentetan bersilang

Memandangkan tiga rentetan s1, s2, s3, sila bantu sahkan sama ada s3 terdiri daripada s1 dan s2 berjalin.

Takrifan dan proses menjalin dua rentetan s dan t adalah seperti berikut, di mana setiap rentetan akan dibahagikan kepada beberapa subrentetan bukan kosong:

s = s1 + s2 + . .. + sn

t = t1 + t2 + ... + tm

|n - m| <= 1

bersambung ialah s1 + t1 + s2 + t2 + s3 + t3 + ... atau t1 + s1 + t2 + s2 + t3 + s3 + ...

Nota: a + b bermaksud rentetan a dan b adalah bercantum.

• Contoh 1:

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

Output: benar

• Contoh 2:

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

Output: palsu

• Contoh 3:

Input: s1 = "", s2 = "", s3 = ""

Output: true

Prompt:

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

0 <= s3.length <= 200

s1, s2 dan s3 semuanya terdiri daripada huruf Inggeris huruf kecil

Kaedah 1: Pengaturcaraan Dinamik (Java)

Persamaan keadaan:

Sempadan 1: dp[0][0] = benar;

Sempadan 2: jika i =0 : dp[0]dp[j] = s2[0-j) sama dengan s3[0,j) Jika palsu ditemui,

sempadan 3 boleh ditinggalkan terus: jika j=0 : dp [i] dp[0] = s1[0-i) bersamaan dengan s3[0,i) Jika palsu ditemui, anda boleh terus meninggalkan

dalam kes lain, capaian (i, j) mungkin daripada ( i-1, j) Ambil langkah seterusnya dan pilih s1[i-1] untuk tiba; 🎜>

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

Salin selepas log masuk

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
}

Atas ialah kandungan terperinci Bagaimana untuk menyelesaikan masalah rentetan interleaved dalam algoritma Go Java?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!