2.8 交替字符串 1. 題目描述 給定三個(gè)字符串s1、s2和s3，判斷第三個(gè)字符串s3是否由前兩個(gè)字符串s1和s2交錯(cuò)而成，即不改變s1和s2中各個(gè)字符原有的相對順序。例如，當(dāng)s1 = "aabcc"，s2 = "dbbca"，s3 = "aadbbcbcac"時(shí)，輸出true；但如果s3 = "accabdbbca"，則輸出false。 2. 分析與解法 這道題不能簡單地排序，因?yàn)橐坏┡判颍蜁?huì)改變s1或s2中各個(gè)字符原始的相對順序。既然不能排序，我們可以考慮使用動(dòng)態(tài)規(guī)劃的方法。 定義dp[i][j]代表s3[0...i+j-1]是否由s1[0...i-1]和s2[0...j-1]的字符組成。如果s1當(dāng)前字符（即s1[i-1]）等于s3當(dāng)前字符（即s3[i+j-1]），且dp[i-1][j]為真，那么可以取s1當(dāng)前字符而忽略s2的情況，dp[i][j]返回真；如果s2當(dāng)前字符等于s3當(dāng)前字符，并且dp[i][j-1]為真，那么可以取s2而忽略s1的情況，dp[i][j]返回真。其他情況下，dp[i][j]返回假。 參考代碼： ```java public boolean IsInterleave(String s1, String s2, String s3) { ??int n = s1.length(), m = s2.length(), s = s3.length(); ??? ??// 如果長度不一致，則s3不可能由s1和s2交錯(cuò)組成 ??if (n + m != s) ????return false; ??? ??boolean[][] dp = new boolean[n + 1][m + 1]; ??? ??// 在初始化邊界時(shí)，我們認(rèn)為空串可以由空串組成，因此dp[0][0]賦值為true。 ??dp[0][0] = true; ??for (int i = 0; i < n + 1; i++) { ????for (int j = 0; j < m + 1; j++) { ??????if (dp[i][j] || (i - 1 >= 0 && dp[i - 1][j] == true && ????????// 取s1字符 ????????s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (j - 1 >= 0 && dp[i][j - 1] == true && ????????// 取s2字符 ????????s2.charAt(j - 1) == s3.charAt(i + j - 1))) ????????dp[i][j] = true; ??????else ????????dp[i][j] = false; ????} ??} ??? ??return dp[n][m]; } ``` 理解本題及上段代碼，對真正理解動(dòng)態(tài)規(guī)劃有一定幫助。 ??