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

Kerumitan masa: O(m*n)

Kerumitan ruang: O(m *n)

kaedah 1: Pengaturcaraan Dinamik (GO)

Kaedah khusus telah diterangkan di atas Sila lihat kandungan di atas untuk butiran.

dp[i][j] bermaksud sama ada aksara i pertama bagi s1 dan aksara j pertama bagi s2 boleh membentuk aksara i+j bagi s3 Jika ya, isikan rentetan itu ialah rentetan kosong

Nyatakan persamaan peralihan: Bahagian atas bukan rentetan kosong dan aksara semasa s1 adalah sama dengan aksara semasa s3, maka rentetan itu sama dengan rentetan atas + aksara semasa daripada s1. Bahagian kiri bukan rentetan kosong dan aksara semasa s2 adalah sama dengan aksara semasa s3 , maka rentetan itu adalah sama dengan rentetan kiri + aksara semasa 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
}

Kerumitan masa: O (m*n)

Kerumitan ruang: O (m*n)

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!