Go Java 알고리즘에서 인터리브 문자열 문제를 해결하는 방법은 무엇입니까?

인터리브된 문자열

세 개의 문자열 s1, s2, s3이 주어지면 s3이 s1과 s2 인터리브로 구성되어 있는지 확인하는 데 도움을 주세요.

두 문자열 s와 t를 인터리빙하는 정의와 프로세스는 다음과 같습니다. 여기서 각 문자열은 비어 있지 않은 여러 하위 문자열로 나뉩니다.

s = s1 + s2 + ... + sn

t = t1 + t2 + ... + tm

|n - m| + ...

참고: 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 <= s1.length, s2.length <= 100

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: j=0인 경우: dp[i]dp[0] = s1[ 0-i )는 s3[0,i)와 같음 false를 만난 후 바로 생략할 수 있습니다.

다른 경우에는 (i, j)에 도달하는 것이 (i-1,j)에서 다음 단계까지일 수 있으며 s1[을 선택합니다. i-1]에 도달하려면 (i,j-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의 현재 문자와 같으면 문자열은 왼쪽 문자와 같습니다. String + 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!