leetcode-algorithms/src/InterleavingString.java at master · anishLearnsToCode/leetcode-algorithms · GitHub

34 lines (30 loc) · 1.27 KB

// https://leetcode.com/problems/interleaving-string

// T: O(n * m)

// S: O(min(m, n))

public class InterleavingString {

public boolean isInterleave(String s1, String s2, String s3) {

if (s1.length() + s2.length() != s3.length()) return false;

if (s1.length() < s2.length()) {

String temp = s1;

s1 = s2;

s2 = temp;

}

final int rows = s1.length() + 1, columns = s2.length() + 1;

final boolean[] dp = new boolean[columns];

for (int row = 0 ; row < rows ; row++) {

for (int column = 0 ; column < columns ; column++) {

if (row == 0 && column == 0) {

dp[column] = true;

} else if (row == 0) {

dp[column] = dp[column - 1] && s2.charAt(column - 1) == s3.charAt(row + column - 1);

} else if (column == 0) {

dp[column] = dp[column] && s1.charAt(row - 1) == s3.charAt(row + column - 1);

} else {

dp[column] = (s1.charAt(row - 1) == s3.charAt(row + column - 1) && dp[column])

|| (s2.charAt(column - 1) == s3.charAt(row + column - 1) && dp[column - 1]);

}

return dp[columns - 1];

}

Expand file tree