【题目描述】
Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.
给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。
【题目链接】
http://www.lintcode.com/en/problem/interleaving-string/
【题目解析】
dp[i][j]表示s1前i个和s2前j个对s3前i+j个是否interleaving string。
首先初始化。遍历s1，初始化所有的dp[i][0]
再遍历s2，初始化所有的dp[0][j]
若s3的第i＋j－1位和s1的第i位相等，则看dp[i-1][j]是否为true；同理，若s3的i+j-1位和s2的第j位相等，则看dp[i][j-1]是否为true。只要两种情况中的任意一种为true，则dp[i][j]为true。
【参考答案】
http://www.jiuzhang.com/solutions/interleaving-string/
原创文章，作者：carmelaweatherly，如若转载，请注明出处：https://blog.ytso.com/tech/opensource/193336.html