【題目描述】

十余年的慶安網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。網(wǎng)絡(luò)營(yíng)銷推廣的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整慶安建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)公司從事“慶安網(wǎng)站設(shè)計(jì)”,“慶安網(wǎng)站推廣”以來，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

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

給出三個(gè)字符串:s1、s2、s3，判斷s3是否由s1和s2交叉構(gòu)成。

【題目鏈接】

http://www.lintcode.com/en/problem/interleaving-string/

【題目解析】

dp[i][j]表示s1前i個(gè)和s2前j個(gè)對(duì)s3前i+j個(gè)是否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/