97. Interleaving String

2019-11-06 08:51:00

字体：大中小

来源：转载

供稿：网友

问题描述 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example, Given: s1 = “aabcc”, s2 = “dbbca”,

When s3 = “aadbbcbcac”, return true. When s3 = “aadbbbaccc”, return false.

解决思路使用动态规划，dp[i][j] 表示 s1[i-1] 和 s2[j-1]能否组合成s3[i+j-1]，若可以，则true，否则false。初始情况：dp[0][0] = true , dp[i][0] = s1[i-1] == s3[i-1] ? dp[i-1][0] : 0 , dp[0][i] = s2[i-1] == s3[i-1] ? dp[0][i-1] : 0 状态转移： if (s3[i+j-1] == s1[i-1]) dp[i][j] = dp[i-1][j]; if (s3[i+j-1] == s2[j-1]) dp[i][j] = dp[i][j-1] || dp[i][j];

代码

class Solution {public: bool isInterleave(string s1, string s2, string s3) { int m = s1.length(); int n = s2.length(); int l = s3.length(); if (m + n != l) return false; else if (m == 0) return s2 == s3; else if (n == 0) return s1 == s3; vector<vector<bool>> dp(m+1,vector<bool>(n+1,false)); dp[0][0] = true; for (int i = 1; i <= m; ++i) dp[i][0] = s1[i-1] == s3[i-1] ? dp[i-1][0] : 0; for (int i = 1; i <= n; ++i) dp[0][i] = s2[i-1] == s3[i-1] ? dp[0][i-1] : 0; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (s3[i+j-1] == s1[i-1]) dp[i][j] = dp[i-1][j]; if (s3[i+j-1] == s2[j-1]) dp[i][j] = dp[i][j-1] || dp[i][j]; } } return dp[m][n]; }};

上一篇：网卡驱动程序的框架以及一个简单的虚拟网卡驱动程序

下一篇：我的第一篇CSDN博客