# Interleaving String

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

## Thoughts

这道题比较非主流。有三个str, 该如何设计f呢？直观的想一下，直接用f\[i]s3前i个字符是否由s1和s2组成。这样没有反应s1和s2的信息。所以不如反过来想，选取s1的前i个，s2的前j个则s3也就固定了。于是f\[i]\[j]为s1的前i个，s2的前j个是否构成了s3的前i+j个字符。

## Code

```
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 m = s1.length();
        int n = s2.length();

        if (s3.length() != m + n) {
            return false;
        }

        // f
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;

        // init
        for (int i = 1; i <= m; i++) {
            if (s1.charAt(i - 1) != s3.charAt(i - 1)) {
                break;
            }
            f[i][0] = true;
        }
        for (int j = 1; j <= n; j++) {
            if (s2.charAt(j - 1) != s3.charAt(j - 1)) {
                break;
            }
            f[0][j] = true;
        }

        // loop
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
                    f[i][j] = true;
                } else if (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
                    f[i][j] = true;
                }
            }
        }

        return f[m][n];
    }
}
```

## Analysis

TC: O(mn)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_ii/interleaving_string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.