We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
出处:LeetCode 算法第97题 给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。 示例 1: 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出: true 示例 2: 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出: false
出处:LeetCode 算法第97题
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出: false
字符串问题,多数都可以采用动态规划
/** * @param {string} s1 * @param {string} s2 * @param {string} s3 * @return {boolean} */ function isInterleave(s1, s2, s3) { if (s1.length s2.length !== s3.length) { return false; } const length1 = s1.length; const length2 = s2.length; const dp = [...Array(length1 1)].map(r => Array(length2 1).fill(false)); for (let r = 0; r <= length1; r ) { for (let c = 0; c <= length2; c ) { if (r === 0 && c === 0) { dp[r][c] = true; } else if (r === 0) { dp[r][c] = dp[r][c - 1] && s2[c - 1] === s3[r c - 1]; } else if (c === 0) { dp[r][c] = dp[r - 1][c] && s1[r - 1] === s3[r c - 1]; } else { dp[r][c] = (dp[r][c - 1] && s3[r c - 1] === s2[c - 1]) || (dp[r - 1][c] && s3[r c - 1] === s1[r - 1]); } } } return dp[length1][length2]; } console.log(isInterleave('aabcc', 'dbbca', 'aadbbcbcac'))
The text was updated successfully, but these errors were encountered:
No branches or pull requests
习题
思路
字符串问题,多数都可以采用动态规划
解答
The text was updated successfully, but these errors were encountered: