Given three strings s1, s2, s3, please help verify whether s3 is composed of s1 and s2 interleaved.
The definition and process of interleaving two strings s and t are as follows, where each string will be divided into several non-empty substrings:
s = s1 s2 .. . sn
t = t1 t2 ... tm
|n - m| <= 1
The staggered is s1 t1 s2 t2 s3 t3 ... or t1 s1 t2 s2 t3 s3 ...
Note: a b means the concatenation of strings a and b.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Example 3:
Input: s1 = "", s2 = "", s3 = ""
Output: true
Prompt:
0 <= s1.length, s2 .length <= 100
0 <= s3.length <= 200
s1, s2, and s3 are all composed of lowercase English letters
State equation:
Boundary 1: dp[0][0] = true;
Boundary 2: if i =0 : dp[0]dp[j] = s2[0-j) equals s3[0,j) If false is encountered, you can directly omit
Boundary 3: if j=0 : dp[i] dp[0] = s1[0-i) equals s3[0,i) If false is encountered, you can directly omit it later
In other cases, reaching (i, j) may be from (i-1,j) Take the next step and select s1[i-1] to arrive; you may also take a step to the right from (i,j-1) and select s2[j-1] to arrive;
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]; } }
Time complexity: O(m*n)
Space complexity: O(m*n)
The specific method has been described above, please see the above content for details.
dp[i][j] means the first i characters of s1, the first j characters of s2, whether they can form the first i j characters of s3, if so, fill in the string, if not, it is an empty string
State transfer equation: If the upper part is not an empty string and the current character of s1 is equal to the current character of s3, then the string is equal to the upper string. The left side of the current character of s1 is not an empty string and the current character of s2 is equal to the current character of s3, then the character The string is equal to the current character of string s2 on the left
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 }
Time complexity: O (m*n)
Space complexity: O (m*n)
The above is the detailed content of How to solve interleaved string problem in Go Java algorithm?. For more information, please follow other related articles on the PHP Chinese website!