Interleaving String

Question

Given three strings: s1, s2, s3,
determine whether s3 is formed by the interleaving of s1 and s2.

Example
For s1 = "aabcc", s2 = "dbbca"

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
Challenge
O(n2) time or better


题解1 - bug

Java

public class Solution {
/**
* Determine whether s3 is formed by interleaving of s1 and s2.
* @param s1, s2, s3: As description.
* @return: true or false.
*/
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = (s1 == null) ? 0 : s1.length();
int len2 = (s2 == null) ? 0 : s2.length();
int len3 = (s3 == null) ? 0 : s3.length();

if (len3 != len1 + len2) return false;

int i1 = 0, i2 = 0;
for (int i3 = 0; i3 < len3; i3++) {
boolean result = false;
if (i1 < len1 && s1.charAt(i1) == s3.charAt(i3)) {
i1++;
result = true;
continue;
}
if (i2 < len2 && s2.charAt(i2) == s3.charAt(i3)) {
i2++;
result = true;
continue;
}

// return instantly if both s1 and s2 can not pair with s3
if (!result) return false;
}

return true;
}
}


题解2

(s1[i1] == s3[i3]) && (s2[i2] == s3[i3]) 时分两种情况考虑，即让 s1[i1] 和 s3[i3] 配对或者 s2[i2] 和 s3[i3] 配对，那么嵌套调用时新生成的字符串则分别为 s1[1+i1:], s2[i2], s3[1+i3:]s1[i1:], s2[1+i2], s3[1+i3:]. 嵌套调用结束后立即返回最终结果，因为递归调用时整个结果已经知晓，不立即返回则有可能会产生错误结果，递归调用并未影响到调用处的 i1 和 i2.

Python

class Solution:
"""
@params s1, s2, s3: Three strings as description.
@return: return True if s3 is formed by the interleaving of
s1 and s2 or False if not.
@hint: you can use [[True] * m for i in range (n)] to allocate a n*m matrix.
"""
def isInterleave(self, s1, s2, s3):
len1 = 0 if s1 is None else len(s1)
len2 = 0 if s2 is None else len(s2)
len3 = 0 if s3 is None else len(s3)

if len3 != len1 + len2:
return False

i1, i2 = 0, 0
for i3 in xrange(len(s3)):
result = False
if (i1 < len1 and s1[i1] == s3[i3]) and \
(i1 < len1 and s1[i1] == s3[i3]):
# s1[1+i1:], s2[i2:], s3[1+i3:]
case1 = self.isInterleave(s1[1 + i1:], s2[i2:], s3[1 + i3:])
# s1[i1:], s2[1+i2:], s3[1+i3:]
case2 = self.isInterleave(s1[i1:], s2[1 + i2:], s3[1 + i3:])
return case1 or case2

if i1 < len1 and s1[i1] == s3[i3]:
i1 += 1
result = True
continue

if i2 < len2 and s2[i2] == s3[i3]:
i2 += 1
result = True
continue

# return instantly if both s1 and s2 can not pair with s3
if not result:
return False

return True


C++

class Solution {
public:
/**
* Determine whether s3 is formed by interleaving of s1 and s2.
* @param s1, s2, s3: As description.
* @return: true of false.
*/
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();

if (len3 != len1 + len2) return false;

int i1 = 0, i2 = 0;
for (int i3 = 0; i3 < len3; ++i3) {
bool result = false;
if (i1 < len1 && s1[i1] == s3[i3] &&
i2 < len2 && s2[i2] == s3[i3]) {
// s1[1+i1:], s2[i2:], s3[1+i3:]
bool case1 = isInterleave(s1.substr(1 + i1), s2.substr(i2), s3.substr(1 + i3));
// s1[i1:], s2[1+i2:], s3[1+i3:]
bool case2 = isInterleave(s1.substr(i1), s2.substr(1 + i2), s3.substr(1 + i3));
// return instantly
return case1 || case2;
}

if (i1 < len1 && s1[i1] == s3[i3]) {
i1++;
result = true;
continue;
}

if (i2 < len2 && s2[i2] == s3[i3]) {
i2++;
result = true;
continue;
}

// return instantly if both s1 and s2 can not pair with s3
if (!result) return false;
}

return true;
}
};


Java

public class Solution {
/**
* Determine whether s3 is formed by interleaving of s1 and s2.
* @param s1, s2, s3: As description.
* @return: true or false.
*/
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = (s1 == null) ? 0 : s1.length();
int len2 = (s2 == null) ? 0 : s2.length();
int len3 = (s3 == null) ? 0 : s3.length();

if (len3 != len1 + len2) return false;

int i1 = 0, i2 = 0;
for (int i3 = 0; i3 < len3; i3++) {
boolean result = false;
if (i1 < len1 && s1.charAt(i1) == s3.charAt(i3) &&
i2 < len2 && s2.charAt(i2) == s3.charAt(i3)) {
// s1[1+i1:], s2[i2:], s3[1+i3:]
boolean case1 = isInterleave(s1.substring(1 + i1), s2.substring(i2), s3.substring(1 + i3));
// s1[i1:], s2[1+i2:], s3[1+i3:]
boolean case2 = isInterleave(s1.substring(i1), s2.substring(1 + i2), s3.substring(1 + i3));
// return instantly
return case1 || case2;
}

if (i1 < len1 && s1.charAt(i1) == s3.charAt(i3)) {
i1++;
result = true;
continue;
}

if (i2 < len2 && s2.charAt(i2) == s3.charAt(i3)) {
i2++;
result = true;
continue;
}

// return instantly if both s1 and s2 can not pair with s3
if (!result) return false;
}

return true;
}
}


题解3 - 动态规划

f[i1][i2] = (s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2]) ||
(s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1])


Python

class Solution:
"""
@params s1, s2, s3: Three strings as description.
@return: return True if s3 is formed by the interleaving of
s1 and s2 or False if not.
@hint: you can use [[True] * m for i in range (n)] to allocate a n*m matrix.
"""
def isInterleave(self, s1, s2, s3):
len1 = 0 if s1 is None else len(s1)
len2 = 0 if s2 is None else len(s2)
len3 = 0 if s3 is None else len(s3)

if len3 != len1 + len2:
return False

f = [[True] * (1 + len2) for i in xrange (1 + len1)]
# s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2]
for i in xrange(1, 1 + len1):
f[i][0] = s1[i - 1] == s3[i - 1] and f[i - 1][0]
# s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1]
for i in xrange(1, 1 + len2):
f[0][i] = s2[i - 1] == s3[i - 1] and f[0][i - 1]
# i1 >= 1, i2 >= 1
for i1 in xrange(1, 1 + len1):
for i2 in xrange(1, 1 + len2):
case1 = s1[i1 - 1] == s3[i1 + i2 - 1] and f[i1 - 1][i2]
case2 = s2[i2 - 1] == s3[i1 + i2 - 1] and f[i1][i2 - 1]
f[i1][i2] = case1 or case2

return f[len1][len2]


C++

class Solution {
public:
/**
* Determine whether s3 is formed by interleaving of s1 and s2.
* @param s1, s2, s3: As description.
* @return: true of false.
*/
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();

if (len3 != len1 + len2) return false;

vector<vector<bool> > f(1 + len1, vector<bool>(1 + len2, true));
// s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2]
for (int i = 1; i <= len1; ++i) {
f[i][0] = s1[i - 1] == s3[i - 1] && f[i - 1][0];
}
// s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1]
for (int i = 1; i <= len2; ++i) {
f[0][i] = s2[i - 1] == s3[i - 1] && f[0][i - 1];
}
// i1 >= 1, i2 >= 1
for (int i1 = 1; i1 <= len1; ++i1) {
for (int i2 = 1; i2 <= len2; ++i2) {
bool case1 = s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2];
bool case2 = s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1];
f[i1][i2] = case1 || case2;
}
}

return f[len1][len2];
}
};


Java

public class Solution {
/**
* Determine whether s3 is formed by interleaving of s1 and s2.
* @param s1, s2, s3: As description.
* @return: true or false.
*/
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = (s1 == null) ? 0 : s1.length();
int len2 = (s2 == null) ? 0 : s2.length();
int len3 = (s3 == null) ? 0 : s3.length();

if (len3 != len1 + len2) return false;

boolean [][] f = new boolean[1 + len1][1 + len2];
f[0][0] = true;
// s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2]
for (int i = 1; i <= len1; i++) {
f[i][0] = s1.charAt(i - 1) == s3.charAt(i - 1) && f[i - 1][0];
}
// s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1]
for (int i = 1; i <= len2; i++) {
f[0][i] = s2.charAt(i - 1) == s3.charAt(i - 1) && f[0][i - 1];
}
// i1 >= 1, i2 >= 1
for (int i1 = 1; i1 <= len1; i1++) {
for (int i2 = 1; i2 <= len2; i2++) {
boolean case1 = s1.charAt(i1 - 1) == s3.charAt(i1 + i2 - 1) && f[i1 - 1][i2];
boolean case2 = s2.charAt(i2 - 1) == s3.charAt(i1 + i2 - 1) && f[i1][i2 - 1];
f[i1][i2] = case1 || case2;
}
}

return f[len1][len2];
}
}