[leetcode] Interleaving String

O(n^2) time or better

解题思路：

s3的第一个字符分别和s1,s2的第一个字符做比较，如果其中一个相同，则去除s3和具有相同前缀的字符串的第一个字符。继续下一轮的比较。最发麻的问题出现了，如果s1和s2的前缀相同，那么选择那个字符串继续比较呢？

这是一个典型的动态规划的问题。借鉴网上分析思路：

dimension dp:

这是一个二维的动态规划，

s1 = "aabcc"s2 = "dbbca"s3 = "aadbbcbcac"

函数

表示子问题：si取前leni个字符的话，那么实际上可以得到这样的一个公式：

由于len3 === len1 + len2，所以这个问题里面实际上存在着两个变量，，是一个二维动态规划题目。从矩阵的角度来看的话，每一个元素的值，依赖于它的上边和左边两个值。

测试集运行时间，解法一3391ms,解法二：2781ms，动态规划还是比较好的解法。

解法一： 传统迭代实现

public boolean isInterleave(String s1, String s2, String s3) {if ((s1.length() + s2.length()) != s3.length())return false;if (s3.length() == 0)return true;else {char c = s3.charAt(0);boolean f = false;if (s1.length() > 0 && s1.charAt(0) == c) {f = isInterleave(s1.substring(1), s2, s3.substring(1));}if (!f && s2.length() > 0 && s2.charAt(0) == c) {f = isInterleave(s1, s2.substring(1), s3.substring(1));}return f;}}解法二： 动态规划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) {boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];if ((s1.length() + s2.length()) != s3.length())return false;for (int i = 0; i < dp.length; i++)for (int j = 0; j < dp[i].length; j++)dp[i][j] = false;dp[0][0] = true;for (int i = 0; i <= s1.length(); i++) {for (int j = 0; j <= s2.length(); j++) {if (dp[i][j]) {if (i != s1.length() && s1.charAt(i) == s3.charAt(i + j))dp[i + 1][j] = true;if (j != s2.length() && s2.charAt(j) == s3.charAt(i + j))dp[i][j + 1] = true;}}}return dp[s1.length()][s2.length()];}}

人的价值，在遭受诱-惑的一瞬间被决定