给三个字符串:s1, s2、s3,确定s3是由s1和s2的交错。
给出三个字符串:s1, s2、s3,判断s3是否由s1和s2交叉构成。
http://www.lintcode.com/en/problem/interleaving-string/
dp[我][j]表示s1前我个和s2前j个对s3前我+ j个是否交错字符串。
首先初始化。遍历s1,初始化所有的dp[我][0]
再遍历s2,初始化所有的dp [0] [j] .
若s3的第i + j - 1位和s1的第我位相等,则看dp(张)[j]是否为真;同理,若s3的i + j - 1位和s2的第j位相等,则看dp[我][j - 1]是否为真实的。只要两种情况中的任意一种为真,则dp[我][j]为真的。
http://www.jiuzhang.com/solutions/interleaving-string/
